1.3：Union-Find算法-----quick-find算法

接下来实现Union-Find算法的第一种实现方式：quick-find算法

首先是数据结构：

我们用一个长度为N的整型数组id[] 来表示图中各个点。一开始初始化id[x] = x，id[x]中x代表点的标号，如果其中两点p, q相连通，则id[p] = id[q]。

find()方法：

只需检查id[p]和id[q]是否相等。

union(p, q)方法：

遍历整个数组，将数组里所有id与id[p]相等的都改成id[p]。

下面是代码实现：

class QuickFindUF {
private int[] id;
private int count;

public QuickFindUF(int n) {
id = new int[n];
for(int i = 0; i < n; i++)
id[i] = i;
count = n;
}

public int count() {
return count;
}

public boolean 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) {
int pid = id[p];
int qid = id[q];

for(int i = 0; i < id.length; i++)
if(id[i] == pid)id[i] = qid;
}
}

对算法的分析：

初始化操作：花费时间级数为N

find():花费时间级数为1

union():在最坏的情况下时间为N