@TOC
并查集是啥子?
- 并查集支持查找一个元素所属的集合,还可以将两个不在一个集合的元素合并。
- 举个栗子,你有家谱去看看到底是不是亲戚。当你的家谱非常庞大,是个大湾子,但是你可以使用并查集来看看你们是不是一个祖宗。
并查集需要那几样东西?
- 需要一个数组pre[n]。
- void join(int m,int n)函数,也就是合并函数。
- int find(itn x)函数。
数组pre[n]
pre[n]的具体意思pre[n]的值表示n的上头, 当pre[4]=8,表示8是4他爸妈。 当一开始,我们没有查家谱,我们就认定自己是自己的祖宗pre[i]=i
int find(int x)函数。
返回值 :find(int x)函数返回自己的祖宗。 就是往一直往自己上头找,知道发现pre[i]==i 表示你找到祖宗了,就返回祖宗。
int find(int n)//找老大
{
int root,son,temp;
root=n;
son=n;
while(root!=pre[root])
root=pre[root];
return root;
}
这个算法还可以进行一下简化。 具体
int find(int n)//找祖宗
{
int root,son,temp;
root=n;
son=n;
while(root!=pre[root])
root=pre[root];
while(son!=root)//压缩一下,直接将所有的人
//直接指向他的祖宗。
{
temp=pre[son];
pre[son]=root;
son=temp;
}
return root;
}
void join(int m,int n)函数
这个函数用于将m和n联合起来,表示他们有一个祖宗。
void join(int m,int n)
{
int i,j;
i=find(m);//找到i的祖宗
j=find(n);
if(i!=j)//两个祖宗相互比较
pre[i]=j;//不同就把一个祖宗归到另一个祖宗,
//也就是认别人为祖宗。
}
最后出个题。 1. 先输入两个数,
- 一个是家谱中查出有多少个关系,
-
一个是有多少人
-
后面一次输入家谱中查出的关系
- 最后输出有多少个家族?
#include<iostream>
using namespace std;
int pre[100];
int find(int n)
{
int root,son,temp;
root=n;
son=n;
while(root!=pre[root])
root=pre[root];
while(son!=root)
{
temp=pre[son];
pre[son]=root;
son=temp;
}
return root;
}
void join(int m,int n)
{
int i,j;
i=find(m);
j=find(n);
if(i!=j)
pre[i]=j;
}
int main()
{
int m,n,a,b,k;
cin>>m>>n;
k=n;
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=0;i<m;i++)
{
cin>>a>>b;
if(find(a)!=find(b))
k--;//找到一个,认一个祖宗,也就是合并一个家族。
join(a,b);
}
cout<<k-1<<endl;
}