package uf; // classes disjointes (union-find) public class UnionFind { private int[] link; private int[] rank; private int numClasses; public UnionFind(int n) { if (n < 0) throw new IllegalArgumentException(); this.link = new int[n]; for (int i = 0; i < n; i++) this.link[i] = i; this.rank = new int[n]; this.numClasses = n; } public int numClasses() { return this.numClasses; } public int find(int i) { if (i < 0 || i >= this.link.length) throw new ArrayIndexOutOfBoundsException(i); int p = this.link[i]; if (p == i) return i; int r = this.find(p); this.link[i] = r; // compression de chemin return r; } public void union(int i, int j) { int ri = this.find(i); int rj = this.find(j); if (ri == rj) return; // déjà dans la même classe this.numClasses--; if (this.rank[ri] < this.rank[rj]) this.link[ri] = rj; else { this.link[rj] = ri; if (this.rank[ri] == this.rank[rj]) this.rank[ri]++; } } public boolean sameClass(int i, int j) { return this.find(i) == this.find(j); } public String toString() { StringBuffer sb = new StringBuffer(); sb.append(this.numClasses); for (int i = 0; i < this.link.length; i++) sb.append("[" + i + "->" + this.link[i] + "]"); return sb.toString(); } } class TestUnionFind { public static void main(String[] args) { UnionFind uf = new UnionFind(8); System.out.println(uf); assert (uf.find(3) == 3); uf.union(1, 5); System.out.println(uf); assert (uf.find(1) == uf.find(5)); assert (uf.find(1) != uf.find(2)); uf.union(0, 7); uf.union(6, 2); uf.union(2, 4); uf.union(0, 3); uf.union(1, 7); System.out.println(uf); for (int i = 0; i < 8; i++) assert (uf.sameClass(i, (i == 0 || i % 2 == 1) ? 0 : 2)); System.out.println(uf); System.out.println("TestUnionFind OK"); } }