ARC037 B バウムテスト

2015/04/19 (Sun) ARC AtCoder グラフ

問題

問題文

方針

連結成分が木かどうかは そこに含まれる辺の数が頂点の数より $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;
    }
}