f260. 愛八卦的同學

題目分析

班上共有編號 0 到 n−1 的同學，並給定 k 組朋友關係 (a, b)。由於題目規定「朋友的朋友」也視為同一小團體，因此可利用並查集 (Disjoint Set) 來進行群組合併與查詢。

並查集 (Disjoint Set)

並查集是一種資料結構，用於維護不相交集合。主要由兩個操作組成：

Find(x) — 尋找所屬集合的根節點

若 x 不是自己的父節點，會將路徑壓縮，使樹更扁平，提高效率。

def find(self, a):
    if self.parent[a] != a:
        self.parent[a] = self.find(self.parent[a])  # 路徑壓縮
    return self.parent[a]

Union(a, b) — 合併 a 與 b 所屬的集合

為避免退化成鏈狀樹，合併時會按大小合併，小樹掛到大樹下，使樹維持高度較小。

def union(self, a, b):
    ra = self.find(a)
    rb = self.find(b)
    if ra == rb:
        return
    if self.size[ra] < self.size[rb]:
        self.parent[ra] = rb
        self.size[rb] += self.size[ra]
    else:
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]

解題流程

輸入直到 EOF，對於每一筆測資，建立 DSU，初始化 n 個人，各自為一組
讀入 k 組朋友 (a, b)，呼叫 union(a, b)
所有合併完成後，對每個人 (i = 0 ~ n-1) 呼叫 find(i)，找出每個的根節點並使用 set() 去除重複
輸出 set 長度即是小團體個數

import sys
input = sys.stdin.readline

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1] * n

    def find(self, a):
        
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]

    def union(self, a, b):
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            self.parent[ra] = rb
            self.size[rb] += self.size[ra]
        else:
            self.parent[rb] = ra
            self.size[ra] += self.size[rb]

while True:
    try:
        n, k = map(int, input().split())
    except:
        break

    dsu = DSU(n)
    for _ in range(k):
        a, b = map(int, input().split())
        dsu.union(a, b)
    roots = set()
    for i in range(n):
        roots.add(dsu.find(i))
    print(len(roots))