d813 - 10583 - Ubiquitous Religions
題目描述
題目要求計算一個大學中學生們最多信了多少種不同的宗教。給定學生數量 n 和學生之間信仰相同的關係數量 m，通過 m 個關係來推斷宗教種類的上限。每個學生最多信一個宗教。
解題思路
這道題可以使用並查集 (Disjoint Set Union) 演算法來解決。並查集用於處理不相交集合的合併和查找。
- 初始化：將每個學生視為一個獨立的集合，即每個學生的 parent 指向自己。
- 合併：遍歷給定的
m個關係，對於每個關係(x, y)，將學生x和學生y所在的集合合併。 - 計算：合併完所有關係後，統計有多少個集合，每個集合代表一種不同的宗教。集合的數量就是宗教種類的上限。
複雜度分析
- 時間複雜度: O(m * α(n))，其中
m是關係的數量，n是學生的數量，α(n)是反阿克曼函數，增長非常慢，可以近似看作常數。因此，時間複雜度近似為 O(m)。 - 空間複雜度: O(n)，用於存儲並查集的 parent 陣列。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int n,m,a[50001],x,y,ca,ans;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline int fd(int xx){
if(xx==a[xx])return xx;
else return a[xx]=fd(a[xx]);
}
inline void un(int xx,int yy){
a[fd(yy)]=fd(xx);
}
int main(){
while(1){
n=read();
m=read();
if(!n)break;
putchar_unlocked('C');
putchar_unlocked('a');
putchar_unlocked('s');
putchar_unlocked('e');
putchar_unlocked(' ');
write(++ca);
putchar_unlocked(':');
putchar_unlocked(' ');
ans=0;
for(int i=1;i<=n;++i)a[i]=i;
while(m--){
x=read();
y=read();
un(x,y);
}
for(int i=1;i<=n;++i)
if(fd(a[i])==i)++ans;
write(ans);
putchar_unlocked('\n');
}
}