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

Question #45499
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 &lt; 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 &gt;= 3 vertices and m &gt;= n - 1 edges to guarantee that G is biconnected.
0

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!