您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 10608 Friends - 並查集求最大朋友圈經典應用

編輯：C++ 入門

UVA 10608 Friends - 並查集維護連通分量最大值

n 個人，m 對朋友關係。朋友具有傳遞性 (A-B, B-C ⇒ A-C)。求最大朋友圈人數。

並查集核心操作

初始化：parent[i] = i
查找：路徑壓縮 find(x) = (parent[x]==x) ? x : parent[x]=find(parent[x])
合併：parent[find(a)] = find(b)

統計最大分量

遍歷所有人，cnt[find(i)]++，最大 cnt 即答案。

完整 AC 代碼 (C++)

#include 
#include 
const int MAXN = 30005;
int parent[MAXN], cnt[MAXN];

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) parent[i] = i;
        memset(cnt, 0, sizeof(cnt));
        
        while (m--) {
            int a, b; scanf("%d%d", &a, &b);
            int ra = find(a), rb = find(b);
            if (ra != rb) parent[ra] = rb;
        }
        
        for (int i = 1; i <= n; i++) cnt[find(i)]++;
        int ans = 0;
        for (int i = 1; i <= n; i++) if (cnt[i] > ans) ans = cnt[i];
        printf("%d\n", ans);
    }
    return 0;
}

Java 版本 (含路徑壓縮優化)

// 同邏輯，Java 遞歸 find 可能棧溢出，建議迭代寫法
int find(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root];
    while (parent[x] != root) {
        int tmp = parent[x];
        parent[x] = root;
        x = tmp;
    }
    return root;
}