バウムテスト
問題
B – バウムテスト
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
記録
- 2022/01/28 UnionFindでやろうとしたが、二重で
.leader()
を使う発想が思いつかず。
解法1
Union-Find
使った閉路判定。- \(u_{i}\) と \(v_{i}\) を
merge
するまえに それぞれのleader
を確認する。 - \(u_{i}\) と \(v_{i}\) の
leader
が同じ場合、merge
すると閉路になる。
コード例1
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; int main() { int N, M; cin >> N >> M; dsu uf(N); vector<int> hasLoop; rep(i, M) { int u, v; cin >> u >> v; --u; --v; if(uf.leader(u) == uf.leader(v)) { hasLoop.push_back(u); } uf.merge(u, v); } int n = hasLoop.size(); set<int> hasLoopRoot; rep(i, n) { int h = hasLoop[i]; hasLoopRoot.insert(uf.leader(h)); } int ans = uf.groups().size(); cout << ans - hasLoopRoot.size() << endl; return 0; }
解法2
DFS
を使った閉路判定。- 各頂点について訪れたことがあるか否かを確認する変数を用意しておく。
DFS
ですでにおとづれたことがある頂点に再度訪れた場合、閉路があることになる。
コード例2
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; int N, M; vector<vector<int>> graph; vector<bool> visited; bool hasLoop; void dfs(int current, int prev) { if(visited[current] == true) { hasLoop = true; return; } visited[current] = true; rep(i, int(graph[current].size())) { int next = graph[current][i]; if(next != prev) { dfs(next, current); } } } int main() { cin >> N >> M; graph.resize(N); visited.resize(N); rep(i, M) { int u, v; cin >> u >> v; --u; --v; graph[u].push_back(v); graph[v].push_back(u); } int ans = 0; rep(i, N) { hasLoop = false; dfs(i, i); if(!hasLoop) { ans++; } } cout << ans << endl; return 0; }