題目連結: https://zerojudge.tw/ShowProblem?problemid=d813
# 內容
這個世界上有許多不同的宗教信仰。你想要知道你就讀的大學中，學生們到底信了多少種不同的宗教。
在你就讀的大學中共有 n 個學生 (0 < n <= 50000)。顯然你不可能對每個人個別詢問他們的信仰，而且某些學生也不方便透露他們所信的宗教。而解決這些問題的一種可能的方法是詢問 m ( 0 <= m <= n (n-1)/2 ) 對學生他們是否信同一個宗教 (例如他們可能一起去某間教堂，會知道他們彼此信相同的宗教 )。由這些資料，即使你沒辦法知道每個人信哪個教，但是你可以估計出他們最多信了多少種不同的宗教。你可以假設每個學生最多信一個宗教。
# 解題思路
就是很基本的並查集阿，最後在掃一次有多少種不同宗教就好啦
# 程式碼
#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; | |
} |
