# Union-Find & Analysis of Algorithms

• This case shows that, how to improve algorithm step by step.

## 1. Dynamic Connectivity

• Given a set of N objects.
• Union command: connect two objects.
• Find/connected query: is there a path connecting the two objects?
• We assume "is connected to" is an equivalence relation:
• Reflexive: p is connected to p.
• Symmetric: if p is connected to q, then q is connected to p.
• Transitive: if p is connected to q and q is connected to r, then p is connected to r.

### 1.1. First Solution: Connected components

• Maximal set of objects that are mutually connected.

### 1.2. Second Solution: Quick Find

• To merge components containing p and q, change all entries whose id equals id[p] to id[q].

### 1.5. Final Solution: Weighted quick-union with path compression

• quick-union:
• weighted: Keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree.
• Keep the depth of any node x is at most lg N.
• path compression: Make every other node in path point to its grandparent.
• Code:

  package week1;

import common.StdIn;

import java.io.FileNotFoundException;
import java.util.Scanner;

public class UnionFind {

private int count;
private int[] parent;
private int[] sz; // record the weight

UnionFind(int n) {
count = n;
parent = new int[n];
sz = new int[n];
for(int i=0; i<n; i++) {
parent[i] = i;
sz[i] = 1;
}
}

public int root(int id) {
while (parent[id] != id) {
parent[id] = parent[parent[id]]; // improve
id = parent[id];
}
return id;
}

public boolean connected(int p, int q) {
return root(p) == root(q);
}

// quick union
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if(sz[rootP] <= sz[rootQ]) {
parent[rootP] = rootQ;
sz[rootQ] += sz[rootP];
} else {
parent[rootQ] = rootP;
sz[rootP] += sz[rootQ];
}
count --;
}

public int count() {
return count;
}

public static void main(String[] args) {
Scanner sc = null;
try {
sc = new Scanner(StdIn.getDataFile("mediumUF.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int n = sc.nextInt();
UnionFind uf = new UnionFind(n);
while (sc.hasNext()) {
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
System.out.println(p + " " + q);
}
System.out.println(uf.count() + " components");
}
}


## 2. Analysis of Algorithms

### 2.1. Common Order-of-growth Classifications

• $1, \log{N}, N \log{N}, N^2, N^3, \text{ and } 2^N$
• $\text{time} = \lg{T(N)}$
• $\text{size} = \lg{N}$

### 2.3. Why Big-Oh Notation

• Formal Definition: $T(n) = O(f(n))$ if and only if there exist constants $c,n_0 > 0$ such that $T(n) \le c \cdot f(n)$ for all $n \ge n_0$
• $T(n)$ is the function of the running time of an algorithm.
• Warning $c, n_0$ cannot depend on n.
• [NOTE] It kinds of says, we use $n^k$, but not $n^{k-1}$
• Because $O(n^{k-1}) = c \cdot n^{k-1}$ will always less then $n^k$ (c is a constant, but n is not).
• And we need that, T(n) is bounded above by a constant multiple of f(n).
• Example