題目連結: https://zerojudge.tw/ShowProblem?problemid=d831
# 內容
多年來友情的羈絆，終於將在這畢業的季節開花結果。
這幾天，班上同學們無時無刻都熱烈討論著畢業旅行的地點。
小明說，如果要去六福村，可以順便去小人國；
小美說，如果去了恆春的話，墾丁就在幾十公里外了，一定也要去玩；
小華表示，小鬼湖跟大鬼湖好像很近，似乎都是很有趣的地方。
身為班長，聽到同學這麼多「去了哪裡也可以去哪裡」的資訊後，
你決定要為班上的同學們，找到一個能玩最多景點的畢業旅行。
# 解題思路
超基本的並查集題目喔～～～
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
int relation[50010]; | |
int find_root(int x) | |
{ | |
if(relation[x]==x) return x; | |
else return relation[x]=find_root(relation[x]); | |
} | |
int main(){ | |
for(int n,m,t=1,cnt=0;cin>>n>>m&&(n||m);t++,cnt=0){ | |
bool relate[50010]={}; | |
for(int i=1;i<=n;relation[i]=i,i++); | |
for(int c=0,i,j;c<m&&cin>>i>>j;c++,relation[find_root(i)]=find_root(j)); | |
for(int i=1;i<=n;i++) | |
if(!relate[find_root(i)]) | |
cnt++,relate[find_root(i)]=true; | |
cout<<"Case "<<t<<": "<<cnt<<"\n"; | |
} | |
return 0; | |
} |
