about_并查集

　　　　前天刚学了并查集，挺好用的，虽然我现在只会用它来解决是不是亲戚啊，是不是朋友啊，带权并查集还不是很理解。

　　　　并查集也叫做不相交集合，主要有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;

　　}

巴特西