ARC 037 B

今回はこの問題です。

arc037.contest.atcoder.jp

n個の頂点とm本の辺からなる無向グラフがあります。このグラフの連結部分のうち、木になっているものはいくつあるか答えなさい、という問題です。

union findを利用しました。解答はこんな感じ。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int parent[101];
     
    int getparent(int n)
    {
        if(parent[n] < 0) return n;
        else return parent[n] = getparent(parent[n]);
    }
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            parent[i] = -1;
        }
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            u = getparent(u);
            v = getparent(v);
            if(u > v) swap(u, v);
            if(u == v){
                parent[u] = -2;
            } else {
                if(parent[u] == -2 || parent[v] == -2){
                    parent[u] = -2;
                    parent[v] = -2;
                } else {
                    parent[v] = u;
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(parent[i] == -1) ans++;
        }
        cout << ans << endl;
        return 0;
    }

parent[i]の値は、頂点iが含まれる部分が木であるときはその木の根のノード番号(ただし頂点iが根であれば-1)が、木でなければ-2になります。これを枝が追加されるごとに更新していきます。
ノードuが含まれる連結部分とノードvが含まれる連結部分をつなぎます。まずそれぞれその部分の根にしておきます。ここで、両方の根が同じになる場合または片方の部分がすでに木ではない場合、uとvのノードを含む部分は木ではなくなってしまいます。したがって、parentの値を-2に更新しておきます。そうでないときはparent[v]の値を更新します。
これを繰り返すことで、最終的にparentの値が-1になっている数だけ木があることになります。