Advanced Programming, Jan-Apr 2015 Assignment 4 17 March, 2015 Due 24 March, 2015 ---------------------------------------------------------------------- NOTE: The usual rules apply about file names for submitting your assignment. ---------------------------------------------------------------------- Filename: scc.py Write a Python program to compute the strongly connected components and the associated scc dag for a directed graph. Here are some specifications. Input The input graph will be given as an adjacency list in the following format. 1. The first line of input is N, the number of vertices. The vertices are labelled 1,2,...,N. 2. The next N lines describe the outgoing edges from vertices 1,2,...,N, respectively. If vertex i has D neighbours {j_1,j_2,...,j_D}, the line for vertex i is given as white-space separated list of D+1 integers D j_1 j_2 j_3 ... j_D The neighbours of each vertex i may be specified in any order; there is no assumption that each list is in ascending order. Output Label each scc by the smallest vertex it contains. For instance, if an scc consists of vertices {3,4,7}, its label is 3. These scc labels can then be used to specify the edges in the scc dag. Print your output in the following format 1. First print the sccs on separate lines. The lines should be in ascending order of scc number and each scc should be a space separated list of vertices in ascending order. 2. Then print the edges of the scc dag using the scc numbers to label the vertices. Print one edge per line, in lexicographic order. Each edge (i,j) should be printed as a space separated pair of integers "i j". Example Consider the following directed graph. 1<-----2 ----->3 ^ ^ | | | | | | v 4<-----5 <-----6 The sccs are {1}, {2,3,5,6}, {4} with labels 1,2,4, respectively and the scc dag has edges (2,1), (2,4) and (4,1). The input for this graph would be as follows: 6 0 2 3 1 1 6 1 1 2 2 4 1 5 Your output should be 1 2 3 5 6 4 2 1 2 4 4 1 ======================================================================