Answer to Question #45499 in Programming & Computer Science for Nafi

Question

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.