Cactus

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10891 🧐 관찰 및 접근 # 어떤 정점이 최대 한개의 사이클에만 속해있다면, 해당 그래프는 정점 선인장이다. $\text{DP}[i]$ : 정점 $i$의 부모와 정점 $i$의 자식을 잇는 tree edge가 아닌 간선의 수라고 정의하자. 어떤 그래프가 정점 선인장일 필요충분조건은 $\forall i$ 에 대해 $\text{DP}[i] \leq 1$인 것이다. 이는 DFS+누적합처럼 계산할 수 있다. 💻 풀이 # 코드 (C++): void dfs(int c, int p, int d){ depth[c] = d; par[c] = p; DP[c] = 0; for(auto n: links[c]){ if(n == p) continue; if(depth[n] == 0){ dfs(n, c, d+1); DP[c] += DP[n]; } else if(depth[n] < depth[c]) DP[c]++; else DP[par[c]]--; } } void solve(){ cin >> N >> M; rep(i, 0, M){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } dfs(1, -1, 1); bool isCactus = true; rep(i, 1, N+1) if(DP[i] > 1) isCactus = false; if(isCactus) cout << "Cactus"; else cout << "Not cactus"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10891 🧐 관찰 및 접근 # 어떤 정점이 최대 한개의 사이클에만 속해있다면, 해당 그래프는 정점 선인장이다. $\text{DP}[i]$ : 정점 $i$의 부모와 정점 $i$의 자식을 잇는 tree edge가 아닌 간선의 수라고 정의하자. 어떤 그래프가 정점 선인장일 필요충분조건은 $\forall i$ 에 대해 $\text{DP}[i] \leq 1$인 것이다. 이는 DFS+누적합처럼 계산할 수 있다. 💻 풀이 # 코드 (C++): void dfs(int c, int p, int d){ depth[c] = d; par[c] = p; DP[c] = 0; for(auto n: links[c]){ if(n == p) continue; if(depth[n] == 0){ dfs(n, c, d+1); DP[c] += DP[n]; } else if(depth[n] < depth[c]) DP[c]++; else DP[par[c]]--; } } void solve(){ cin >> N >> M; rep(i, 0, M){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } dfs(1, -1, 1); bool isCactus = true; rep(i, 1, N+1) if(DP[i] > 1) isCactus = false; if(isCactus) cout << "Cactus"; else cout << "Not cactus"; } 🔒 구현 코드 잠금