# 【題解】ZeroJudge d831: 畢業旅行

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d831
【解題想法】並查集，Disjoint Set Union-Find algorithm (DSU)

```#include <iostream>
using namespace std;
int p[1000005];
int n, m, mx, a, b;

int find(int a){
if (p[a] < 0) return a;
else {
p[a] = find(p[a]);
return p[a];
}
}

int main() {
while (cin >> n >> m){
for (int i = 0; i < n; i++){
p[i] = -1;
}
mx = 1;
for (int i = 0; i < m; i++){
cin >> a >> b;
a = find(a);
b = find(b);
if (a != b){
p[a] += p[b];
mx = max(mx, -p[a]);
p[b] = a;
}
}
cout << mx << "\n";
}
}
```

Python code (credit: Amy Chou)

```def Find(x):
# 初始值 p[x] = -1 表示指向自己
if p[x] < 0:
return x
else:
# 順便做「路徑壓縮」
p[x] = Find(p[x])
return p[x]

def Union(x, y):
g1 = Find(x)
g2 = Find(y)
if g1 != g2:
# 加總元素個數(負值)
# p[]:只有「代表元素」的值是存「元素個數」，其它的存「代表元素編號」
p[g1] += p[g2]
p[g2] = g1
#=== main ===
while True:
try:
N, M = map(int, input().split())
# 初始值 p[x] = -1 表示自成一群，「代表元素」是自己
p = [-1 for i in range(N)]
mx = 1
for _ in range(M):
a, b = map(int, input().split())
g1 = Find(a)
g2 = Find(b)
if (g1 != g2):
p[g1] += p[g2]
p[g2] = g1
mx = max(mx, -p[g1])
print(mx)
except:
break
```