ARC037 B バウムテスト
問題
方針
連結成分が木かどうかは そこに含まれる辺の数が頂点の数より $1$ 少ないかどうかで判定できます。 そうなっている連結成分の数を数えます。
実装
struct UnionFind {
vector<int> par;
int cnt;
UnionFind(int size_) : par(size_, -1), cnt(size_) { }
bool set(int x, int y) {
x = find(x); y = find(y);
if (x != y) {
if (par[y] < par[x]) swap(x, y);
par[x] += par[y]; par[y] = x;
cnt--;
}
return x != y;
}
bool get(int x, int y) {
return find(x) == find(y);
}
int find(int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
int size(int x) {
return -par[find(x)];
}
int size() {
return cnt;
}
};
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N;
while(cin >> N){
int M;
cin >> M;
UnionFind u(N);
vi deg(N);
rep(i,M){
int a,b;
cin >> a >> b;
a--; b--;
u.set(a,b);
deg[a]++;
deg[b]++;
}
map<int,vi> m;
rep(i,N){
m[u.find(i)].pb(i);
}
int ans = 0;
for(auto & p : m){
int e = 0;
for(auto & v : p.second){
e += deg[v];
}
e /= 2;
ans += e==p.second.size()-1;
}
cout << ans << endl;
}
}