UVa 10583
題目
http://domen111.github.io/UVa-Easy-Viewer/?10583
有 $n$ 個人，每個人至多有 $1$ 個宗教信仰，現在給你 $m$ 對數字 $i, j$ ，表示 $i, j$ 擁有相同的宗教信仰。求在這 $n$ 個人當中最多有多少不同的宗教信仰?
想法
這裡可以想到並查集的概念
我們可以將這 $n$ 個人分成幾個集合，而每個集合都有一個老大，並且該集合內的所有人都會指向老大
這樣一來，當我們要判定一個人所在的群組是否已經被算過的話，就可以透過遞迴的方式找到群組的老大，看看老大有沒有被算過即可，也就是將集合以老大表示。
另外，在並查集當中有個優化的方式，也就是在遞迴查詢的過程當中，順便將詢問的人指向最終查詢到的老大，如此一來下次在詢問的時候就可以避免再次遞迴。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
using namespace std;
int head[50005],n,m,p,q,ans=0,Case=1;
bool vis[50005];
int Find(int x){
if(head[x]==x)
return x;
return head[x] = Find(head[x]);
}
void Union(int x, int y){
head[Find(x)] = Find(y);
}
int main(){
while(cin>>n>>m && (n!=0 && m!=0)){
for(int i=0 ; i<50005 ; i++){
head[i]=i;
vis[i]=false;
}
ans=0;
for(int i=0 ; i<m ; i++){
cin>>p>>q;
Union(p,q);
}
for(int i=1,tmp ; i<=n ; i++){
tmp=Find(i);
if(!vis[tmp]){
vis[tmp]=true;
ans++;
}
}
cout<<"Case "<<Case++<<": "<<ans<<"\n";
}
return 0;
}
|
複雜度分析
預處理以及輸入的時間複雜度皆約為 $O(n)$
每次 Union 的操作時間複雜度約為 $O(log(n))$
Find 的時間複雜度也約為 $O(log(n))$
總時間複雜度約為 $O(n + (n+m)log(n))$ ，不過實際上應該會更快