[UVA] 10608 - Friends

題目連結

我的做法：
Disjoint set 同一群選一個代表！

==================================================
程式碼：
/* 題目: UVa 10608 - Friends
 * Language: C++
 * Created on: 2016年12月16日
 *   Author: hanting
 */
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class DisjointSet
{
    vector<int> rep;
public:
    void init(int n)
    {
        rep.assign(n, -1);
    }
    int Find(int x)
    {
        if(rep[x] < 0) return x;
        else return rep[x] = Find(rep[x]);
    }
    void Union(int x, int y)
    {
        int fx = Find(x),
            fy = Find(y);
        if(fx != fy)
        {
            if(rep[fx] <= rep[fy])
            {
                rep[fx] += rep[fy];
                rep[fy] = fx;
            }
            else
            {
                rep[fy] += rep[fx];
                rep[fx] = fy;
            }
        }
    }
    int groupN(int x)
    {
        int fx = Find(x);
        return -rep[fx];
    }
};
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        DisjointSet dSet;
        int nodeN, edgeN;
        cin >> nodeN >> edgeN;
        dSet.init(nodeN+1);
        int s, t;
        for(int i = 0; i < edgeN; i++)
        {
            //cin >> s >> t;
            scanf("%d%d", &s, &t);
            dSet.Union(s, t);
        }
        int maxi = 0;
        for(int i = 1; i <= nodeN; i++)
        {
            maxi = max(maxi, dSet.groupN(i));
        }
        cout << maxi << endl;
    }
    return 0;
}