并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集合。
- Union：将两个子集合并成同一个集合。
其实判断一个图是否存在环已经有相应的算法，此文用并查集来判断一个图是否有环。
我们可以用一个一维数组parent[] 来记录子集合。
看下面这个图：
0
|
|
1——2
对每一条边的两个顶点加入集合，发现两个相同的顶点在一个子集合中，就说明存在环。
初始化：parent[n] 的每个元素都为-1，共有n个子集合，表示集合只有当前顶点一个元素
0 1 2
-1 -1 -1
然后逐个处理每条边。
边0-1：我们找到两个子集合 0 和1，因为他们在不同的子集合，现在需要合并他们(Union). 把其中一个子集合作为对方的父集合.
0 1 2 <----- 1 成为 0 的 父集合 (1 现在代表集合 {0, 1})
1 -1 -1
边0-2:1属于属于子集合1,2属于子集合2，因此合并他们。
0 1 2 <----- 2 作为 1的父集合 (2 现在代表集合 {0, 1, 2})
1 2 -1
边0-2: 0是在子集和2和2也是在子集合2， 因为 0->1->2 // 1 是0 父集合 并且 2 是1的父集合 。因此，找到了环
// 用并查集判断是否存在环 002 #include <stdio.h> 003 #include <stdlib.h> 004 #include <string.h> 005 006 // 图中的边 007 struct Edge 008 { 009 int src, dest; 010 }; 011 012 // 图结构体 013 struct Graph 014 { 015 // V-> 顶点个数, E-> 边的个数 016 int V, E; 017 018 // 每个图就是 边的集合 019 struct Edge* edge; 020 }; 021 022 // 创建一个图 023 struct Graph* createGraph(int V, int E) 024 { 025 struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) ); 026 graph->V = V; 027 graph->E = E; 028 029 graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) ); 030 031 return graph; 032 } 033 034 // 查找元素i 所在的集合( 根 ) 035 int find(int parent[], int i) 036 { 037 if (parent[i] == -1) 038 return i; 039 return find(parent, parent[i]); 040 } 041 042 // 合并两个集合 043 void Union(int parent[], int x, int y) 044 { 045 int xset = find(parent, x); 046 int yset = find(parent, y); 047 parent[xset] = yset; 048 } 049 050 // 检测环 051 int isCycle( struct Graph* graph ) 052 { 053 int *parent = (int*) malloc( graph->V * sizeof(int) ); 054 055 // 初始化所有集合 056 memset(parent, -1, sizeof(int) * graph->V); 057 058 // 遍历所有边 059 for(int i = 0; i < graph->E; ++i) 060 { 061 int x = find(parent, graph->edge[i].src); 062 int y = find(parent, graph->edge[i].dest); 063 064 if (x == y) //如果在一个集合，就找到了环 065 return 1; 066 067 Union(parent, x, y); 068 } 069 return 0; 070 } 071 072 // 测试 073 int main() 074 { 075 /* 创建一些的图 076 0 077 | 078 | 079 1-----2 */ 080 struct Graph* graph = createGraph(3, 3); 081 082 // 添加边 0-1 083 graph->edge[0].src = 0; 084 graph->edge[0].dest = 1; 085 086 // 添加边 1-2 087 graph->edge[1].src = 1; 088 graph->edge[1].dest = 2; 089 090 // 添加边 0-2 091 graph->edge[2].src = 0; 092 graph->edge[2].dest = 2; 093 094 if (isCycle(graph)) 095 printf( "Graph contains cycle" ); 096 else 097 printf( "Graph doesn't contain cycle" ); 098 099 return 0; 100 }