//  find 的原始实现int find(int parent[], int i){    if (parent[i] == -1)        return i;    return find(parent, parent[i]);}// union()的原始实现void Union(int parent[], int x, int y){    int xset = find(parent, x);    int yset = find(parent, y);    parent[xset] = yset;}

假设有4个元素 0, 1, 2, 3初始化0 1 2 3 Do Union(0, 1)   1   2   3    / 0Do Union(1, 2)     2   3       /   1 /0Do Union(2, 3)         3            /      2     /   1 /0

继续用上面的例子0 1 2 3 Do Union(0, 1)   1   2   3    / 0Do Union(1, 2)   1    3 /  0    2Do Union(2, 3)    1     /  |  0   2   3

假设集合{0, 1, .. 9} 的树表示如下所示：  当调用 find(3)时              9         /    |    \          4     5      6     /     \        /      0        3     7    8            /             1    2  我们向上查找，找到是这个集合的根节点. 路径压缩就是：直接把 3的 父节点 设置为 9当下次再查找 1, 2 或 3 时，查找的路径就会变短。               9         /    /  \            4    5    6     3      /           /  \   /      0           7    8  1   2

// 用并查集判断是否存在环#include<stdio.h>#include<stdlib.h>#include<string.h>//图中的边struct Edge{    int dest,src;};//图结构体struct Graph{// V-> 顶点个数, E-> 边的个数    int V,E;    // 每个图就是 边的集合    struct Edge *edge;};struct subset{    int parent;    int rank;};//创建一个图struct Graph * createGraph(int V, int E){    struct Graph *graph=(struct Graph *)malloc(sizeof(struct Graph));    graph->V=V;    graph->E=E;    graph->edge=(struct Edge *)malloc(graph->E*sizeof(struct Edge));    return graph;}//使用路径压缩int find(struct subset subsets[],int i){// 找到 root并使  root 作为 i 的父节点    if(subsets[i].parent==i)        return i;    else        return (subsets[i].parent=find(subsets,subsets[i].parent));}//使用按秩合并void Union(struct subset subsets[], int x, int y){    int xroot=find(subsets,x);    int yroot=find(subsets,y);     // 将深度较小的集合 合并到深度大的集合下面    if(subsets[xroot].rank<subsets[yroot].rank)        subsets[xroot].parent=yroot;    else if(subsets[xroot].rank>subsets[yroot].rank)        subsets[yroot].parent=xroot;    else//深度一样，任选一个，并增加另一个    {        subsets[yroot].parent=xroot;        subsets[xroot].rank++;    }}int isCycle(struct Graph* graph){    int V=graph->V;    int E=graph->E;    struct subset *subsets=(struct subset *)malloc(V*sizeof(struct subset));    for(int i=0;i<V;i++)    {        subsets[i].parent=i;        subsets[i].rank=0;    }    for(int e=0;e<E;e++)    {        int x=find(subsets,graph->edge[e].dest);        int y=find(subsets,graph->edge[e].src);        if(x==y)            return 1;        Union(subsets,x,y);    }    return 0;}int main(){    int V=3,E=2;    struct Graph *graph=createGraph(V,E);  /* 构造以下的图         0        |          |            1-----2 */    graph->edge[0].src=http://www.mamicode.com/0;    graph->edge[0].dest=1;    graph->edge[1].src=http://www.mamicode.com/1;    graph->edge[1].dest=2;    // graph->edge[2].src=http://www.mamicode.com/0;>//graph->edge[2].dest=3;    if(isCycle(graph))        printf("Graph contains cycle\n");    else        printf("Graph doesn‘t contains cycle\n");    return 0;}