UVA10608 Friends

Graph, Union Find

출처: UVA UVA10608 Friends


SOL)
유니온 파인드의 merge를 할때마다 합쳐지는 쪽으로
원소의 수를 더해준다.


[-] Collapse

#include<stdio.h>
#include<vector>
using namespace std;

struct Union_Find{
    vector<int> parent, rank, num;
    int component;
    Union_Find(int n) :parent(n + 1), rank(n + 1), num(n+1,1), component(n){
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (parent[u] == u) return u;
        return find(parent[u]);
    }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
        component--;
        num[v] += num[u];
        num[u] = 0;
        return true;
    }
};
int n, m;
int main(){
    //freopen("input.txt", "r", stdin);
    int testCase;
    scanf("%d", &testCase);
    while (testCase--){
        scanf("%d%d", &n, &m);
        Union_Find uf(n);
        for (int i = 0; i < m; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            uf.merge(u, v);
        }
        if (m == 0) {
            printf("0\n");
            continue;
        }
        int max = 0;
        for (int i = 1; i <= n; i++)
        if (max < uf.num[i]) max = uf.num[i];
        printf("%d\n", max);
    }
}