本篇并查集的實作為最初級，目的是為了能夠讓入門的小伙伴了解并查集的思想，我會以hdu1213為例子，給大家詳細解釋，
題目鏈接
原題為英文，為了方便小伙伴們，我將提煉了一下題意，
有n個人一起吃飯，有些人相互認識，認識的人想坐在一起，不想跟陌生人坐，例如A認識B，B認識C，那么A,B,C會坐在一張桌子上，給出認識的人，問需要多少張桌子，
輸入：
T<=25，代表輸入資料組數
1<=N,M<=1000，N代表人數，M代表這兩個人互相認識，
接下來M行，每行輸入兩個數字A,B，中間有空格，
輸出：每組輸出一個數字，加上換行（杭電Oj對格式比較嚴格不按要求可能會PE）
并查集核心：
查找：
找到該下標所在的集合
int find_set(int x)
{
return x==people[x]?x:find_set(people[x]);//此處為查找
}
合并：
合并兩個集合
void union_set(int x,int y)
{
x = find_set(x);
y = find_set(y);
if(x!=y)people[x] = people[y];//合并兩個集合
}
合并和查找復雜度均為O(n)，
完整代碼：
#include<iostream>
using namespace std;
int people[1010];
int find_set(int x)
{
return x==people[x]?x:find_set(people[x]);
}
void union_set(int x,int y)
{
x = find_set(x);
y = find_set(y);
if(x!=y)people[x] = people[y];
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++)pe[i] = i;//初始化
for(int i=1;i<=m;i++){
cin>>a>>b;
union_set(a,b);//合并
}
int ans = 0;
for(int i=1;i<=n;i++)
if(pe[i] == i)//統計有多少個集合
ans++;
cout<<ans<<endl;//輸出答案
}
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261103.html
標籤：其他
上一篇：海康SDK/大華SDK安防視頻智能分析平臺EasyCVR接入過多通道卡頓解決
下一篇：Linux下的基礎IO