【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d813 (考生答對率: 2.46%)
【解題想法】並查集
#include <iostream>
using namespace std;
const int maxn = 50000+5;
int pa[maxn];
int Find(int x){
return pa[x] == x ? x : pa[x] = Find(pa[x]);
}
bool Union(int x, int y){
int g1 = Find(x);
int g2 = Find(y);
if (g1 == g2) return false;
else{
pa[g2] = g1;
return true;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, x, y, Case = 1;
while (cin >> n >> m && n+m){
for (int i = 0; i < maxn; i++){
pa[i] = i;
}
int ans = n;
while (m--){
cin >> x >> y;
if (Union(x, y)) {
ans--;
}
}
cout << "Case " << Case++ << ": ";
cout << ans << "\n";
}
return 0;
}
Python code (credit: Amy Chou)
- 注意:測資最後並非以 0 0 結束。
import sys
def Find(x):
if (pa[x] == x):
return x
else:
pa[x] = Find(pa[x])
return pa[x]
def Union(x, y):
g1 = Find(x)
g2 = Find(y)
if (g1 == g2):
return False
else:
pa[g2] = g1
return True
lines = sys.stdin.readlines()
idx = -1
Case = 0
while True:
try:
idx += 1
n, m = map(int, lines[idx].split())
if n == 0 and m == 0:
break
Case += 1
pa = []
for i in range(n+1):
pa.append(i)
ans = n
for i in range(m):
idx += 1
x, y = map(int, lines[idx].split())
if (Union(x, y)):
ans -= 1
print(f"Case {Case}: {ans}")
except:
break