1) Describe, in pseudo-code, an O(n + m)-time algorithm for computing all the connected components of an undirected graph G with n vertices and m edges.
2) Say that an n-vertex directed acyclic graph G is compact if there is some way of numbering the vertices of G with the integers from 0 to n - 1 such that G contains the edge (i; j) if and only if i < j, for all i; j in [0; n - 1]. Give an O(n^2)-time algorithm for detecting if G is compact.
3) Computer networks should avoid single points of failure, that is, network nodes that can disconnect the network if they fail. We say a connected graph G is biconnected if it contains no vertex whose removal would divide G into two
or more connected components. Give an O(n + m)-time algorithm for adding at most n edges to a connected graph G, with n >= 3 vertices and m >= n - 1 edges to guarantee that G is biconnected.

## Comments

## Leave a comment