CS213 Assignment 4-Strongly connected graphs Solution

This assignment has 4 problems related to strongly connected directed graphs. All 4 are independent of each other, though the solutions are based on similar ideas. A spanning subgraph of a graph is obtained by deleting some edges from the graph, keeping all the nodes.
For all these problems, the input is a directed graph. The first line of input will specify n, m and op, where n is the number of nodes, m is the number of edges and op ∈ {0,1,2,3} is the problem to be solved. The next m lines will specify the edges, each line containing two numbers i,j, indicating an edge (i,j). It can be assumed that the input graph satisfies any conditions required for the problem to be solved. Assume 2 ≤ n ≤ 105 and 0 ≤ m ≤ 106. The nodes can be assumed to be {0,...,n − 1}. The output for each problem is a list of edges. The first line should give the number of edges, and then the edges must be printed, one per line. An edge (i,j) is specified by printing i and j in that order, separated by a space. The order of printing the edges does not matter.
0. It is known that every strongly connected directed graph with n ≥ 2 nodes has a spanning strongly connected subgraph with at most 2n − 2 edges, and this is best possible. Given a strongly connected directed graph with n ≥ 2 nodes, you have to find a strongly connected spanning subgraph with at most 2n − 2 edges. The output should be the number of edges in the subgraph, followed by the edges in the subgraph, printed one per line in any order. (There is no efficient algorithm known to find a spanning strongly connected subgraph with minimum number of edges).
2. A directed graph is said to be oriented if for all edges (i,j), (j,i) is not an edge. In other words, the binary relation defined by the edges is asymmetric. Given a strongly connected directed graph, you have to find whether there exists a spanning oriented subgraph which is also strongly connected. In other words, if for some nodes i,j, both (i,j) and (j,i) are edges in the graph, you have to delete at least one of the two edges, preserving the strongly connected property of the graph. If there is no such subgraph, print “impossible” else print “possible”. If it is possible, print out the edges in any such subgraph, one per line, in any order.
3. Given an arbitrary directed graph, find the minimum number of edges that need to beadded to it to make the resulting graph strongly connected. Print out the number and one possible set of edges.
1