Algorithm, Part I Princeton University 公开课第一周 Union－Find算法

Union-Find with Weighted Union and find path compression

一个使用Union－Find的例子  使用Java语言描述

public class SocialNetwork{public void main(String[] args){}public class UnionFind{private int[] id;private int[] sz;private int nCount;private boolean bAllConnected;// we use the path compressprivate int root(int i){while(i != id[i]){id[i] = id[id[i]]; i = id[i];}return i;}public UnionFind(int n){nCount = n;bAllConnected = false;id = new int[n];sz = new int[n];for(int i = 0; i < n; i++){id[i] = i;sz[i] = 1;}}public boolean connected(int p, int q){