算法第四版第一章

public class UF { private int[] id; private int count; public UF(int N){ // 初始化分量Id数组 count=N; id= new int[N]; for (int i = 0; i <N ; i++) { id[i] = i; } } 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){ //将pq归并到相同的分量中 int pId=find(p); int qId=find(q); //如果P和q已经在相同的分量之中则不需要采取任何行动 if(pId==qId) return; //将P的分量重命名为q的名称 for (int i = 0; i <id.length ; i++) { if (id[i]==pId) id[i]=qId; } count--; } public static void main(String[] args) { //解决有in得到的动态连通性问题 Scanner scanner = new Scanner(System.in); int N = Integer.parseInt(scanner.nextLine()); UF uf = new UF(N); System.out.println("请告诉输出多少个数据"); int i=Integer.parseInt(scanner.nextLine()); int j=0; while (j<i){ int p= scanner.nextInt(); int q= scanner.nextInt(); j++; if (uf.connected(p,q)) { continue; }//如果已经连通就忽略 uf.union(p,q); System.out.println(p+" " +q); } System.out.println(uf.count() + 0+" components"); } private int find2(int p){ //找出分量名称 while (p!=id[p]) p=id[p]; return p; } //对union的改进0 public void union2(int p,int q){ //将P和q的根节点统一 int pRoot = find(p); int qRoot = find(q); if (pRoot == qRoot) return; id[pRoot] =qRoot; count--; } }

 

优化版

public class WeightedQuickUnionUF { private int[] parent; // parent[i] = parent of i 父链接数组 private int[] size; // size[i] = number of sites in subtree rooted at i 各个节点所对应的分量大小 private int count; // number of components 连通分量的数量 public WeightedQuickUnionUF(int n) { count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public int count() { return count; } public int find(int p) { validate(p); while (p != parent[p]) p = parent[p]; return p; } // validate that p is a valid index private void validate(int p) { int n = parent.length; if (p < 0 || p >= n) { throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1)); } } public boolean connected(int p, int q) { return find(p) == find(q); } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // make smaller root point to larger one if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } else { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } count--; } public static void main(String[] args) { int n = StdIn.readInt(); edu.princeton.cs.algs4.WeightedQuickUnionUF uf = new edu.princeton.cs.algs4.WeightedQuickUnionUF(n); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.connected(p, q)) continue; uf.union(p, q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + " components"); } }