何謂并查集
并查集實(shí)際上就是并集和查集的過程非驮。那么什么是集呢？你可以把他近似地理解為一棵樹。即一個(gè)根結(jié)點(diǎn)連著無數(shù)個(gè)子節(jié)點(diǎn)阐肤。
并查集的實(shí)現(xiàn)
給出例題：例題源網(wǎng)站（洛谷）
這里附：
題目描述
如題，現(xiàn)在有一個(gè)并查集讲坎，你需要完成合并和查詢操作孕惜。
輸入輸出格式
輸入格式：
第一行包含兩個(gè)整數(shù)N、M晨炕，表示共有N個(gè)元素和M個(gè)操作衫画。
接下來M行，每行包含三個(gè)整數(shù)Zi瓮栗、Xi削罩、Yi
當(dāng)Zi=1時(shí)，將Xi與Yi所在的集合合并
當(dāng)Zi=2時(shí)费奸，輸出Xi與Yi是否在同一集合內(nèi)弥激，是的話輸出Y；否則話輸出N
輸出格式：
如上货邓，對(duì)于每一個(gè)Zi=2的操作秆撮，都有一行輸出，每行包含一個(gè)大寫字母换况，為Y或者N
輸入輸出樣例
輸入樣例#1：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
輸出樣例#1：
N
Y
N
Y
這就是最最基礎(chǔ)的并查集模版了
初始化
我們會(huì)用到一個(gè)father數(shù)組职辨，記錄每一個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)
最初要把每一個(gè)節(jié)點(diǎn)都當(dāng)作一個(gè)集盗蟆，即
father[i]=i;
這里我們需要用一個(gè)循環(huán)來實(shí)現(xiàn)，完整代碼如下
for(int i=1;i<=n;/*n即n個(gè)元素*/i++)
father[i]=i;
然后初始化就完成啦舒裤。喳资。
函數(shù)
并查集一定會(huì)用到一個(gè)getfather函數(shù)（其實(shí)名字你隨便起）
這個(gè)函數(shù)就是去找根節(jié)點(diǎn)
int getfather(int x)//找x的根結(jié)點(diǎn)
{//這其實(shí)是一個(gè)遞歸函數(shù)
if(father[x]==x)//邊界條件，如果x的根結(jié)點(diǎn)就是x（也就是說它沒有更上邊的祖宗了）
return x;//就會(huì)返回x的值
else
{
father[x]=getfather(father[x]); //不然的話就會(huì)一級(jí)一級(jí)找上去（先找到它爸爸腾供，在找到它爸爸的爸爸仆邓，再找到它爸爸的爸爸的爸爸。伴鳖。节值。。榜聂。）
}
return father[x];
}
讀入
先上代碼吧搞疗。。畢竟沒什么難度
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&z[i],&x[i],&y[i]);
z1[i]=getfather(x[i]);//z1數(shù)組用于存儲(chǔ)每一個(gè)x[i]的根結(jié)點(diǎn)
z2[i]=getfather(y[i]);//z2數(shù)組用于存儲(chǔ)每一個(gè)y[i]的根結(jié)點(diǎn)
}
并集
目的就是讓一個(gè)集合的根結(jié)點(diǎn)成為另一個(gè)集合的根結(jié)點(diǎn)须肆，這樣這兩個(gè)集合就有同一個(gè)根結(jié)點(diǎn)匿乃，就起到了合并的作用。（比如說小明的爺爺也是小李的爺爺豌汇，他倆就是親戚）
代碼如下
if(z[i]==1)
{
if (z1[i]!=z2[i])
Union(z1[i],z2[i]);
}
這個(gè)Union是我自己寫的一個(gè)函數(shù)幢炸，它長這樣：
void Union(int xx,int yy)
{
int f1=getfather(xx);//f1就是 xx的根結(jié)點(diǎn)
int f2=getfather(yy);//f2就是yy的根結(jié)點(diǎn)
father[f1]=f2;//讓xx的根結(jié)點(diǎn)成為yy的根結(jié)點(diǎn)（上面有解釋）
return;
}
由于這是一個(gè)void函數(shù)，所以你也可以直接把代碼 粘出來拒贱。
查集
鑒于我們已經(jīng)做過并集的工作宛徊，查集就變得輕松了很多，我們只需要確認(rèn)兩個(gè)點(diǎn)是否有 同一個(gè)根結(jié)點(diǎn)就行了柜思，代碼如下：
if(z[i]==2)
{
if(getfather(x[i])==getfather(y[i]))//如果 x[i]的根結(jié)點(diǎn)就是y[i]的根結(jié)點(diǎn)
{
cout<<"Y"<<endl;//就輸出y
}
else
{
cout<<"N"<<endl;//不然就輸出 n
}
}
應(yīng)該不難懂吧岩调？
本題完整代碼如下
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,father[200000];
int z[200000],y[200000],x[200000];
int getfather(int x)
{
if(father[x]==x)
return x;
else
{
father[x]=getfather(father[x]);
}
return father[x];
}
void Union(int xx,int yy)
{
int f1=getfather(xx);
int f2=getfather(yy);
father[f1]=f2;
return;
}
int main()
{
int z1[200000],z2[200000];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
father[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&z[i],&x[i],&y[i]);
z1[i]=getfather(x[i]);
z2[i]=getfather(y[i]);
}
for(int i=1;i<=m;i++)
{
if(z[i]==1)
{
if (z1[i]!=z2[i])
Union(z1[i],z2[i]);
}
if(z[i]==2)
{
if(getfather(x[i])==getfather(y[i]))
{
cout<<"Y"<<endl;
}
else
{
cout<<"N"<<endl;
}
}
}
return 0;
}
還是建議自己去寫一遍。
這里還有幾道題
極其類似模版的題
局域網(wǎng)
營救
不會(huì)的可以自己去看一下題解赡盘。
tks
