在文章《Union-Find 操作检测无向图有无环算法》中介绍了 Union-Find 算法的一个简单实现，使用一维数组来处理不相交集合数据结构（Disjoint-set data structure）。

Union-Find 算法为该数据结构提供了两种非常有用的操作：

• Find：判断子集中是否存在特定的元素。可以用于检测是否两个元素存在于相同的子集中。

• Union：将两个不子集合并成新的子集合。

 1   private int Find(int[] parent, int i)
 2   {
 3     if (parent[i] == -1)
 4       return i;
 5     return Find(parent, parent[i]);
 6   }
 7 
 8   private void Union(int[] parent, int x, int y)
 9   {
10     int xset = Find(parent, x);
11     int yset = Find(parent, y);
12     parent[xset] = yset;
13   }

上述算法的实现的运行时间是 O(n)。

另一种实现方式是使用有根树来表示集合，树中的每个节点都包含集合的一个成员，每棵树表示一个集合，形成不相交集合森林（Disjoint-set forest）。每棵树的根包含了集合的代表，并且是它自己的父节点。

如上图中，(a) 中两棵树表示两个集合 {b, c, e, h} 和 {d, f, g}，其中 c 和 f 是代表。(b) 为 Union(e, g) 的结果。

实际上，上面这种树的表示法不会比采用链表表示的算法更快。但是，通过引入两种启发式策略，可以获得目前已知的、渐进意义上最快的不想交集合数据结构。

• 第一种启发式策略是按秩合并（Union by Rank），其思想是使包含较少节点的树的根指向包含较多节点的树的根。

• 第二种启发式策略是路径压缩（Path Compression），在 Find 操作中，使查找路径上的每个节点都直接指向根节点。路径压缩并不改变节点的秩（Rank）。

如上图中，(a) 为执行 Find 操作之前的表示集合的树；(b) 为执行 Find(a) 操作后的树，查找路径上的每个节点都直接指向了根。

通过两种启发式策略对运行时间的改进，新的算法的运行时间为 O(logn)。

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 
  5 namespace GraphAlgorithmTesting
  6 {
  7   class Program
  8   {
  9     static void Main(string[] args)
 10     {
 11       Graph g = new Graph(6);
 12       g.AddEdge(0, 1, 16);
 13       g.AddEdge(0, 2, 13);
 14       g.AddEdge(1, 2, 10);
 15       g.AddEdge(1, 3, 12);
 16       //g.AddEdge(2, 1, 4);
 17       g.AddEdge(2, 4, 14);
 18       //g.AddEdge(3, 2, 9);
 19       g.AddEdge(3, 5, 20);
 20       //g.AddEdge(4, 3, 7);
 21       //g.AddEdge(4, 5, 4);
 22 
 23       Console.WriteLine();
 24       Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
 25       Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
 26       Console.WriteLine();
 27 
 28       Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle());
 29 
 30       Console.ReadKey();
 31     }
 32 
 33     class Edge
 34     {
 35       public Edge(int begin, int end, int weight)
 36       {
 37         this.Begin = begin;
 38         this.End = end;
 39         this.Weight = weight;
 40       }
 41 
 42       public int Begin { get; private set; }
 43       public int End { get; private set; }
 44       public int Weight { get; private set; }
 45 
 46       public override string ToString()
 47       {
 48         return string.Format(
 49           "Begin[{0}], End[{1}], Weight[{2}]",
 50           Begin, End, Weight);
 51       }
 52     }
 53 
 54     class Subset
 55     {
 56       public int Parent { get; set; }
 57       public int Rank { get; set; }
 58     }
 59 
 60     class Graph
 61     {
 62       private Dictionary<int, List<Edge>> _adjacentEdges
 63         = new Dictionary<int, List<Edge>>();
 64 
 65       public Graph(int vertexCount)
 66       {
 67         this.VertexCount = vertexCount;
 68       }
 69 
 70       public int VertexCount { get; private set; }
 71 
 72       public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } }
 73 
 74       public IEnumerable<Edge> Edges
 75       {
 76         get { return _adjacentEdges.Values.SelectMany(e => e); }
 77       }
 78 
 79       public int EdgeCount { get { return this.Edges.Count(); } }
 80 
 81       public void AddEdge(int begin, int end, int weight)
 82       {
 83         if (!_adjacentEdges.ContainsKey(begin))
 84         {
 85           var edges = new List<Edge>();
 86           _adjacentEdges.Add(begin, edges);
 87         }
 88 
 89         _adjacentEdges[begin].Add(new Edge(begin, end, weight));
 90       }
 91 
 92       private int Find(Subset[] subsets, int i)
 93       {
 94         // find root and make root as parent of i (path compression)
 95         if (subsets[i].Parent != i)
 96           subsets[i].Parent = Find(subsets, subsets[i].Parent);
 97 
 98         return subsets[i].Parent;
 99       }
100 
101       private void Union(Subset[] subsets, int x, int y)
102       {
103         int xroot = Find(subsets, x);
104         int yroot = Find(subsets, y);
105 
106         // Attach smaller rank tree under root of high rank tree
107         // (Union by Rank)
108         if (subsets[xroot].Rank < subsets[yroot].Rank)
109           subsets[xroot].Parent = yroot;
110         else if (subsets[xroot].Rank > subsets[yroot].Rank)
111           subsets[yroot].Parent = xroot;
112 
113         // If ranks are same, then make one as root and increment
114         // its rank by one
115         else
116         {
117           subsets[yroot].Parent = xroot;
118           subsets[xroot].Rank++;
119         }
120       }
121 
122       public bool HasCycle()
123       {
124         Subset[] subsets = new Subset[VertexCount];
125         for (int i = 0; i < subsets.Length; i++)
126         {
127           subsets[i] = new Subset();
128           subsets[i].Parent = i;
129           subsets[i].Rank = 0;
130         }
131 
132         // Iterate through all edges of graph, find subset of both
133         // vertices of every edge, if both subsets are same, 
134         // then there is cycle in graph.
135         foreach (var edge in this.Edges)
136         {
137           int x = Find(subsets, edge.Begin);
138           int y = Find(subsets, edge.End);
139 
140           if (x == y)
141           {
142             return true;
143           }
144 
145           Union(subsets, x, y);
146         }
147 
148         return false;
149       }
150     }
151   }
152 }