Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class QuickUnion {
- private int[] id; // id[i] = parent of i
- private int count; // number of components
- // instantiate N isolated components 0 through N-1
- public QuickUnion(int N) {
- id = new int[N];
- count = N;
- for (int i = 0; i < N; i++) {
- id[i] = i;
- }
- }
- // return number of connected components
- public int count() {
- return count;
- }
- // return root of component corresponding to element p
- public int find(int p) {
- while (p != id[p])
- p = id[p];
- return p;
- }
- // are elements p and q in the same component?
- public boolean connected(int p, int q) {
- return find(p) == find(q);
- }
- // merge components containing p and q
- public void union(int p, int q) {
- int i = find(p);
- int j = find(q);
- if (i == j) return;
- id[i] = j;
- count--;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement