数据结构的性质会直接影响算法的效率。这里，以触点为索引，触点和连接分量都是用 int 值表示，将会使用分量中某个触点的值作为分量的标识符。所以，一开始，每个触点都是只含有自己的分量，分量标识符为触点的值。由此，可以初步实现一部分方法：
public class FirstUnionFind:IUnionFind
private int[] id;//* 分量id 以触点作为索引
private int count;//分量数量
public FirstUnionFind(int n)
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
id[i] = i; // 第一个 i 作为触点，第二个 i 作为触点的值
public int Count()
return count;
public bool Connected(int p, int q)
return Find(p) == Find(q);
public int Find(int p)
public void Union(int p, int q)
public class QuickFindUF: IUnionFind
private int[] id;//* 分量id 以触点作为索引
private int count;//分量数量
public QuickFindUF(int n)
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
id[i] = i; // 第一个 i 作为触点，第二个 i 作为触点的值
public int Count()
return count;
public bool Connected(int p, int q)
return Find(p) == Find(q);
public int Find(int p)
return id[p];
public void Union(int p, int q)
var pID = Find(p);
var qID = Find(q);
if (pID == qID)
return;
for (var i = 0; i < id.Length; i++)
if (id[i] == qID)
id[i] = pID;
count--; //连通分量减少
public void Show()
for(var i = 0;i<id.Length;i++)
Console.WriteLine("索引："+i+",值："+ id[i] );
Console.WriteLine("连通分量数量："+count);
在实现 Find() 方法时，从给定触点，链接到另一个触点，知道到达根触点，即链接指向自己。同时修改 Union() 方法，分别找到 p q 的根触点，将其中一个根触点链接到根触点。
public class QuickUnionUF : IUnionFind
private int[] id;
private int count;
public QuickUnionUF(int n)
count = n;
id = new int[n];
for (var i = 0; i < n; i++)
id[i] = i; // 第一个 i 作为触点，第二个 i 作为触点的值
public int Count()
return count;
public bool Connected(int p, int q)
return Find(p) == Find(q);
public int Find(int p)
while (p != id[p])
p = id[p];
return p;
public void Union(int p, int q)
var pRoot = Find(p);
var qRoot = Find(q);
if (pRoot == qRoot)
return;
id[pRoot] =qRoot;
count--; //连通分量减少
public void Show()
for (var i = 0; i < id.Length; i++)
Console.WriteLine("索引：" + i + ",值：" + id[i]);
Console.WriteLine("连通分量数量：" + count);
简单改动就可以避免 quick-union算法 出现最坏情况。quick-union算法 union 方法是随意将一棵树连接到另一棵树，改为总是将小树连接到大树，这需要记录每一棵树的大小，称为加权quick-union算法。
public class WeightedQuickUnionUF: IUnionFind
int[] sz;//以触点为索引的 各个根节点对应的分量树大小
private int[] id;
private int count;
public WeightedQuickUnionUF(int n)
count = n;
id = new int[n];
sz = new int[n];
for (var i = 0; i < n; i++)
id[i] = i; // 第一个 i 作为触点，第二个 i 作为触点的值
sz[i] = 1;
public int Count()
return count;
public bool Connected(int p, int q)
return Find(p) == Find(q);
public int Find(int p)
while (p != id[p])
p = id[p];
return p;
public void Union(int p, int q)
var pRoot = Find(p);
var qRoot = Find(q);
if (pRoot == qRoot)
return;
if (sz[pRoot] < sz[qRoot])
id[pRoot] = qRoot;
id[qRoot] = pRoot;
count--; //连通分量减少
public void Show()
for (var i = 0; i < id.Length; i++)
Console.WriteLine("索引：" + i + ",值：" + id[i]);
Console.WriteLine("连通分量数量：" + count);
