f260 - 愛八卦的同學
題目描述
題目要求計算一個圖中連結元件的數量。圖的節點代表班上的同學，邊代表同學之間的友誼關係。連結元件可以被視為小團體，題目要求輸出小團體的數量。
解題思路
這題可以使用 Disjoint Set (也稱為 Union-Find) 資料結構來解決。Disjoint Set 是一種用於處理不相交集合的資料結構，它提供了兩個主要操作：
find(x): 找到包含元素 x 的集合的代表元素。union(x, y): 將包含元素 x 和 y 的集合合併。
在解題過程中，我們首先初始化每個同學都屬於自己的獨立集合。然後，對於每一對朋友 (a, b)，我們使用 union(a, b) 操作將他們所在的集合合併。最後，統計剩餘的獨立集合數量，即為小團體的數量。
複雜度分析
- 時間複雜度: O(n * α(n) + k * α(n))，其中 n 是同學數量，k 是友誼關係數量，α(n) 是反阿克曼函數，它增長非常慢，可以近似視為常數。因此，時間複雜度可以簡化為 O(n + k)。
- 空間複雜度: O(n)，用於儲存 Disjoint Set 的 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 a[100000];
inline int fd(int x){
if(a[x]==x)return x;
return a[x]=fd(a[x]);
}
inline void un(int x,int y){
a[fd(a[x])]=fd(a[y]);
}
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 read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
int n,k;
while(n=read()){
k=read();
int x,y,ans=n;
for(int i=0;i<n;++i)a[i]=i;
while(k--){
x=read();
y=read();
if(fd(x)!=fd(y)){
un(x,y);
--ans;
}
}
write(ans);
putchar_unlocked('\n');
}
}