21.1 Disjoint-set operations

21.1-1

Suppose that $\text{CONNECTED-COMPONENTS}$ is run on the undirected graph $G = (V, E)$, where $V = \{a, b, c, d, e, f, g, h, i, j, k\}$ and the edges of $E$ are processed in the order $(d, i)$, $(f, k)$, $(g, i)$, $(b, g)$, $(a, h)$, $(i, j)$, $(d, k)$, $(b, j)$, $(d, f)$, $(g, j)$, $(a, e)$. List the vertices in each connected component after each iteration of lines 3–5.

$$ \begin{array}{c|lllllllllll} \text{Edge processed} & \\ \hline initial & \{a\} & \{b\} & \{c\} & \{d\} & \{e\} & \{f\} & \{g\} & \{h\} & \{i\} & \{j\} & \{k\} \\ (d, i) & \{a\} & \{b\} & \{c\} & \{d, i\} & \{e\} & \{f\} & \{g\} & \{h\} & & \{j\} & \{k\} \\ (f, k) & \{a\} & \{b\} & \{c\} & \{d, i\} & \{e\} & \{f, k\} & \{g\} & \{h\} & & \{j\} & \\ (g, i) & \{a\} & \{b\} & \{c\} & \{d, i, g\} & \{e\} & \{f, k\} & & \{h\} & & \{j\} & \\ (b, g) & \{a\} & \{b, d, i, g\} & \{c\} & & \{e\} & \{f, k\} & & \{h\} & & \{j\} & \\ (a, h) & \{a, h\} & \{b, d, i, g\} & \{c\} & & \{e\} & \{f, k\} & & & & \{j\} & \\ (i, j) & \{a, h\} & \{b, d, i, g, j\} & \{c\} & & \{e\} & \{f, k\} & & & & & \\ (d, k) & \{a, h\} & \{b, d, i, g, j, f, k\} & \{c\} & & \{e\} & & & & & & \\ (b, j) & \{a, h\} & \{b, d, i, g, j, f, k\} & \{c\} & & \{e\} & & & & & & \\ (d, f) & \{a, h\} & \{b, d, i, g, j, f, k\} & \{c\} & & \{e\} & & & & & & \\ (g, j) & \{a, h\} & \{b, d, i, g, j, f, k\} & \{c\} & & \{e\} & & & & & & \\ (a, e) & \{a, h, e\} & \{b, d, i, g, j, f, k\} & \{c\} & & & & & & & & \end{array} $$

So, the connected components that we are left with are $\{a, h, e\}$, $\{b, d, i, g, j, f, k\}$, and $\{c\}$.

21.1-2

Show that after all edges are processed by $\text{CONNECTED-COMPONENTS}$, two vertices are in the same connected component if and only if they are in the same set.

First suppose that two vertices are in the same connected component. Then there exists a path of edges connecting them. If two vertices are connected by a single edge, then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed, so all vertices on the path will be in the same set, including the endpoints. Now suppose two vertices $u$ and $v$ wind up in the same set. Since every vertex starts off in its own set, some sequence of edges in $G$ must have resulted in eventually combining the sets containing $u$ and $v$. From among these, there must be a path of edges from $u$ to $v$, implying that $u$ and $v$ are in the same connected component.

21.1-3

During the execution of $\text{CONNECTED-COMPONENTS}$ on an undirected graph $G = (V, E)$ with $k$ connected components, how many times is $\text{FIND-SET}$ called? How many times is $\text{UNION}$ called? Express your answers in terms of $|V|$, $|E|$, and $k$.

Find set is called twice on line 4, this is run once per edge in the graph, so, we have that find set is run $2|E|$ times. Since we start with $|V|$ sets, at the end only have $k$, and each call to $\text{UNION}$ reduces the number of sets by one, we have that we have to made $|V| - k$ calls to $\text{UNION}$.