ARC 032 B

今回はこの問題です。

arc032.contest.atcoder.jp

n個の町とm本の道路があります。それぞれの道路はa[i]とb[i]の町をつないでいます。
現在の状況に対して新たに道路を加えることで任意の町同士を行き来できるようにしたいです。
このとき新たに作らないといけない道路の本数の最小値を求めましょう、という問題です。

回答はこちら。

    #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
     
    vector<int> uf(100001, -1);
     
    int getparent(int n)
    {
        if(uf[n] == -1){
            return n;
        } else {
            return uf[n] = getparent(uf[n]);
        }
    }
     
    int main()
    {
        int n, m;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            a = getparent(a);
            b = getparent(b);
            if(a == b) continue;
            if(a > b) swap(a, b);
            uf[b] = getparent(a);
        }
        int ans = -1;
        for(int i = 1; i <= n; i++){
            if(uf[i] == -1) ans++;
        }
        cout << ans << endl;
        return 0;
    }

union-findっぽいものを使いました。親になっているものの数から1引いたものが答えになります。
道が増えるごとに、aとbが属しているグループの親同士をつないでいきます。uf[i]には頂点iの親を記録していきます。
親になっているものは、ufの値が-1となっているのでそれを数えていけばオッケーです。

親同士をつなげる、というのを忘れてaとb同士をつなげていたので何回もWAしました。気をつけましょう。