前天刚学了并查集,挺好用的,虽然我现在只会用它来解决是不是亲戚啊,是不是朋友啊,带权并查集还不是很理解。
并查集也叫做不相交集合,主要有3个操作,初始化,查找,合并。
并查集其中一个很大的应用就是kruskal嘛。
并查集就是说,有n个元素嘛,我们把每个元素初始化为一个集合,然后不断查找,看看是不是有关系,有的话就合并。
代码手打,无语法高亮,其实是我不知道怎么弄,囧。
const int MAXN=1000+10;//最大点数
int father[MAXN];
int rank[MAXN];//用于按秩合并,使查找速度更快
void make_set(int x)
{
father[x]=x;
rank[x]=0;
}
int find_set(int x)
{
if(father[x]==x)
return x;
else
return father[x]=find_set(father[x]);
}//路径压缩
void union_set(int x,int y)
{
x=find_set(x);
y=find_set(y);
if(x==y)
return ;
if(rank[x]>rank[y])
father[y]=x;
else
{
if(rank[x]==rank[y])
rank[y]++;
father[x]=y;
}
}