Bad Networks

An Internet network can be modeled using a directed graph G = (V, E): The set of nodes V consists of one node for every server in the network and there is an edge (u,v) E if and only if there is a direct link from server u to server v. Any server within a strongly connected component can send and receive packets to and from any server within the same strongly connected component. To ensure uninterrupted connectivity on the network, the networks are usually designed in such a way that there are more than one simple path between every pair of vertices. Then if any link goes down, the packets can still be routed using the remaining links.

In this problem we are interested in detecting really bad networks. Given a directed graph G = (V, E) design an algorithm that determines if there is at most one path between every pair of nodes in G. For full credit, your algorithm should run in O(V(V+E)) time.

(a) Write the pseudocode.

(b) Explain why it works.

(c) Analyze its asymptotic run time.