Last active
August 29, 2015 13:56
-
-
Save advancedxy/9033895 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class HeightedQuickUnionUF { | |
private int[] id; // id[i] = parent of i | |
private int[] height; // sz[i] = number of objects in subtree rooted at i | |
private int count; // number of components | |
// Create an empty union find data structure with N isolated sets. | |
public HeightedQuickUnionUF(int N) { | |
count = N; | |
id = new int[N]; | |
height = new int[N]; | |
for (int i = 0; i < N; i++) { | |
id[i] = i; | |
height[i] = 0; | |
} | |
} | |
// Return the number of disjoint sets. | |
public int count() { | |
return count; | |
} | |
// Return component identifier for component containing p | |
public int find(int p) { | |
while (p != id[p]) { | |
id[p] = id[id[p]]; //point element to its grandparent, path compression, works in practice. | |
p = id[p]; | |
} | |
return p; | |
} | |
// Are objects p and q in the same set? | |
public boolean connected(int p, int q) { | |
return find(p) == find(q); | |
} | |
// Replace sets containing p and q with their union. | |
public void union(int p, int q) { | |
int i = find(p); | |
int j = find(q); | |
if (i == j) return; | |
// make smaller root point to larger one | |
if (height[i] < height[j]) { id[i] = j;} | |
else { | |
id[j] = i; | |
if (height[i] == height[j]) //only h[i] == h[j], we need update height | |
height[i] += 1; //update height by adding 1 | |
} | |
count--; | |
} | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Network { | |
private WeightedQuickUnionUF wuf; | |
public Network(int n) { | |
wuf = new WeightedQucikUnionUF(n); | |
} | |
pulic void connect(int i, int j) { | |
wuf.union(i, j); | |
} | |
public boolean isAllConnected() { | |
return wuf.count == 1; | |
} | |
public static int main(String[] args) { | |
int m = Integer.parseInt(args[0]); | |
In in = new In(args[1]); // input file.every line is t, i, j | |
Network net = new Network(m); | |
while (!in.isEmpty()) { | |
int t = in.readInt(); | |
int i = in.readInt(); | |
int j = in.readInt(); | |
net.connect(i,j) | |
if (net.isAllConnected()) { | |
return t; | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/**************************************************************************** | |
* Compilation: javac WeightedQuickUnionLargestUF.java | |
* Execution: java WeightedQuickUnionLargestUF < input.txt | |
* Dependencies: StdIn.java StdOut.java | |
* | |
* Weighted quick-union (with one line variant path compression). | |
* | |
****************************************************************************/ | |
public class WeightedQuickUnionLargestUF { | |
private int[] id; // id[i] = parent of i | |
private int[] sz; // sz[i] = number of objects in subtree rooted at i | |
private int[] largest; // largest[i] = largest element in the subtree rooted at i | |
private int count; // number of components | |
// Create an empty union find data structure with N isolated sets. | |
public WeightedQuickUnionLargestUF(int N) { | |
count = N; | |
id = new int[N]; | |
sz = new int[N]; | |
largest = new int[N]; | |
for (int i = 0; i < N; i++) { | |
id[i] = i; | |
largest[i] = i; | |
sz[i] = 1; | |
} | |
} | |
// Return the number of disjoint sets. | |
public int count() { | |
return count; | |
} | |
// Return component identifier for component containing p | |
public int realFind(int p) { | |
while (p != id[p]) { | |
id[p] = id[id[p]]; //point element to its grandparent, path compression, works in practice. | |
p = id[p]; | |
} | |
return p; | |
} | |
// fake find, return the largest element in the component | |
public int find(int p) { | |
int root = realFind(p); | |
return largest[root]; | |
} | |
// Are objects p and q in the same set? | |
public boolean connected(int p, int q) { | |
return realFind(p) == realFind(q); | |
} | |
// Replace sets containing p and q with their union. | |
public void union(int p, int q) { | |
int i = realFind(p); | |
int j = realFind(q); | |
if (i == j) return; | |
// make smaller root point to larger one | |
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; largest[j] = Math.max(largest[i], largest[j]); } | |
else { id[j] = i; sz[i] += sz[j]; largest[i] = Math.max(largest[i], largest[j]); } | |
count--; | |
} | |
public static void main(String[] args) { | |
int N = StdIn.readInt(); | |
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N); | |
// read in a sequence of pairs of integers (each in the range 0 to N-1), | |
// calling find() for each pair: If the members of the pair are not already | |
// call union() and print the pair. | |
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"); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment