initialize(n)

initializes data structure with n elements

void union(p, q)

connects element p and q

boolean connected(p, q)

returns whether elements p and q are connected

int find(p)

returns the component identifier of element p

int count()

returns the number of components in the data structure

Quick Find (QF)

Click here to expand...

public class QuickFindUF {
 
	private int[] id;
 
	public QuickFindUF(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
 
	public boolean connected(int p, int q) {
		return id[p] == id[q];
	}
 
	public void union(int p, int q) {
		int pid = id[p];
		int qid = id[q];
		for (int i = 0; i < id.length; i++)
			if (id[i] == pid) id[i] = qid;
	}
}

𝑁

𝑂(𝑁)

𝑂(1)

Quick Union (QU)

Click here to expand...

public class QuickUnionUF {
 
	private int[] id;
 
	public QuickUnionUF(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
 
	public boolean connected(int p, int q) {
		return root(p) == root(q);
	}
 
	public void union(int p, int q) {
		int i = root(p);
		int j = root(q);
		id[i] = j;
	}
 
	private int root(int i) {
		while (i != id[i]) i = id[i];
		return i;
	}
}

𝑁

𝑂(𝑁)

𝑂(𝑁)

Weighted QU

Click here to expand...

public class WeightedQuickUnionUF {
 
	private int[] id;
	private int[] size;
 
	public WeightedQuickUnionUF(int N) {
		id = new int[N];
		size = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			size[i] = 1;
		}
	}
 
	public boolean connected(int p, int q) {
		return root(p) == root(q);
	}
 
	public void union(int p, int q) {
		int pRoot = root(p);
		int qRoot = root(q);
		if (pRoot == qRoot) {
			// do nothing
		} else if (size[pRoot] > size[qRoot]) {
			size[pRoot] += size[qRoot];
			id[qRoot] = pRoot;
		} else {
			size[qRoot] += size[pRoot];
 			id[pRoot] = qRoot; 
		}
	}
 
	private int root(int i) {
		while (i != id[i]) i = id[i];
		return i;
	}
}

𝑁

𝑂(𝑙𝑔𝑁)

𝑂(𝑙𝑔𝑁)

QU + Path Compression

Click here to expand...

public class QuickUnionPathCompressionUF {
 
	private int[] id;
 
	public QuickUnionPathCompressionUF(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}
 
	public boolean connected(int p, int q) {
		return root(p) == root(q);
	}
 
	public void union(int p, int q) {
		int i = root(p);
		int j = root(q);
		id[i] = j;
	}
 
	private int root(int i) {
		int root = i;
		while (root != id[root]) root = id[root];
		while (i != id[i]) id[i] = root;
		return root;
	}
}

𝑁

Weight QU + Path Compression

Click here to expand...

public class WeightedQuickUnionUF {
 
	private int[] id;
	private int[] size;
 
	public WeightedQuickUnionUF(int N) {
		id = new int[N];
		size = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			size[i] = 1;
		}
	}
 
	public boolean connected(int p, int q) {
		return root(p) == root(q);
	}
 
	public void union(int p, int q) {
		int pRoot = root(p);
		int qRoot = root(q);
		if (pRoot == qRoot) {
			// do nothing
		} else if (size[pRoot] > size[qRoot]) {
			size[pRoot] += size[qRoot];
			id[qRoot] = pRoot;
		} else {
			size[qRoot] += size[pRoot];
 			id[pRoot] = qRoot; 
		}
	}
 
 	private int root(int i) {
		int root = i;
		while (root != id[root]) root = id[root];
		while (i != id[i]) id[i] = root;
		return root;
	} 
}

𝑁