f677 - FJCU_109_Winter_Day3_Lab1 並查集練習
題目描述
題目描述了傳染病的傳播問題。給定 N 個人和 M 個接觸關係，其中 0 號染病，需要找出所有與 0 號直接或間接接觸的人，即需要隔離的人數。
解題思路
本題可以使用並查集 (Disjoint Set Union) 演算法來解決。並查集可以有效地追蹤每個人的連通性。初始時，將每個人視為一個獨立的集合。然後，遍歷接觸關係，將接觸的人所在的集合合併。最後，找出所有與 0 號在同一個集合中的人，這些人就需要隔離。程式碼中，fa 函數用於查找集合的代表元素，main 函數用於讀取輸入、建立並查集、合併集合以及計算隔離人數。
複雜度分析
- 時間複雜度: O(M * N + N)，其中 M 是接觸關係的數量，N 是人數。最壞情況下，
fa函數需要遍歷整個集合，而合併操作需要遍歷所有元素。 - 空間複雜度: O(N)，用於儲存並查集的父節點陣列
a。
程式碼
#include <iostream>
using namespace std;
int a[1001],ans;
int fa(int n){
if(n==a[n])return n;
return a[n]=fa(a[n]);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,m,x,y;
cin >> n >> m;
for(int i=0;i<n;++i){
a[i]=i;
}
while(m--){
cin >> x >> y;
int ca=fa(a[x]),cb=fa(a[y]),cc=min(ca,cb);
for(int i=0;i<n;++i){
if(fa(a[i])==ca||fa(a[i])==cb){
a[i]=cc;
}
}
}
for(int i=0;i<n;++i){
if(fa(a[i])==0){
++ans;
}
}
cout << ans;
}