BRAVE

AOJ BRAVE

 

Graph (Union Find)

 

SOL)

Union_Find를 이용하여 서로 연결된 컴포넌트들을 묶어주고

이때 묶인 컴포넌트의 원소의수가 가장 큰 것이 답이다.

[-] Collapse

#include<cstdio>
#include<vector>
using namespace std;
struct Union_Find{
    int components;
    vector<int> parent, rank;
    Union_Find(int n) :parent(n), rank(n), components(n){
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (u == parent[u]) return u;
        return parent[u] = 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];
        components--;
        return true;
    }
};

int main(){
    int T; scanf("%d", &T);
    while (T-- > 0){
        int N, C; scanf("%d%d", &N, &C);
        Union_Find uf(N + 1);
        vector<int> count(N + 1);
        int ans = 0;


        for (int i = 0; i < C; i++){
            int u, v; scanf("%d%d", &u, &v);
            uf.merge(u, v);
        }

        for (int i = 1; i <= N; i++){
            int parent = uf.find(i);
            count[parent]++;
            if (ans < count[parent]) ans = count[parent];
        }

        printf("%d\n", ans);
    }
    return 0;
}