IITKESO207A_3P_1  Strongly connected components
Given a digraph G = (V, E), print the strongly connected component graph G_{SCC} = (V_{SCC}, E_{SCC}).
Labeling of vertices in V_{SCC} should be done as follows:
For vertex v in V_{SCC} , let us define orderid(v) = min{label(v_{i})  v_{i} is part of v in V_{SCC}}
Vertex v in V_{SCC} with lowest value of orderid(v) gets label 0, vertex with second lowest value gets label 1 and so on.
Input
The graph is given in the adjacency list format. The first number is n, the number of vertices, which will be an integer ≥ 1. The vertex set is assumed to be V = {0, 1, . . . , n − 1}. Following this number n, there are n lines, where, the i^{th} line (1^{st} , 2^{nd} ...) corresponds to the adjacency list of node numbered i1 (0,1,...). Each adjacency list is a sequence of vertex ids (between 0 and n − 1) and ends with 1.
Output
Print the number of strongly connected components.
From the next line , print the sorted adjacency list of each SCC appended with 1
Constraints
2 <= n <= 1000
TIme  1s
Example 1:
Input:
9
1 1
4 3 2 1
5 1
1
0 1
6 1
7 1
8 1
2 1
Output:
3
1 2 1
1
1
Explanation:
In the above example, there will be 3 SCCs : {0, 1, 4}, {2, 5, 6, 7, 8} and {3}.
SCCs of {0, 1, 4}, {2, 5, 6, 7, 8}, {3} have orderids 0, 2 and 3 respectively. Therefore, {0, 1, 4} gets label 0, {2, 5, 6, 7, 8} gets label 1 and {3} gets label 2. There are two edges (0, 1) and (0, 2) in the condensed graph G_{SCC}. Verify the same in the following diagram:
Example 2:
Input:
10
1 1
9 1
4 5 7 9 1
4 1
1
4 1
1 8 1
1
1
1 1
Output:
9
1 1
1
1 4 5 7 1
4 1
1
4 1
1 8 1
1
1
hide comments
umeshku:
20171023 23:23:49
can you please provide us one more test case just to be double sure about our code. My code is working fine for above 2 test cases but not for hidden test cases.


Programming Club, IITK:
20171023 06:48:07
@mkrishna1: No. It doesn't matter. You can always sort if you need to. Data sets are small. 

mkrishna1:
20171022 18:07:17
Are adjacency lists sorted in input?


Programming Club, IITK:
20171020 20:48:46
@nikhilbl: No. All redundant multiple edges should be dropped. All selfloops should be dropped. 

nikhilbl:
20171020 14:58:14
Last edit: 20171020 14:59:34 

nikhilbl:
20171020 14:37:44
Can one strongly connected component have multiple edges to another SCC? 

Programming Club, IITK:
20171018 09:47:59
Some of you are not sorting the adjacency list before printing and getting a lot of wrong answers. We have highlighted the word "sorted", so that you notice its importance. And then there are others, who are not giving importance to labeling vertices appropriately. Please read problem statement carefully. Last edit: 20171018 09:55:32 

Programming Club, IITK:
20171018 09:41:52
@sronin: New line at the end does not matter, we ignore the extra whitespaces 

sronin:
20171018 08:30:45
is there a new line in the end? 

Programming Club, IITK:
20171016 10:33:10
Just to let you know guys: There are total 10 test cases. Test case #16 are small cases where n<=100 and test cases #710 are large cases where 250<=n<=1000. Whenever you submit your solution, you will receive additional info regarding status of judge for each of the cases. [Click on the result "runtime error"/"wrong answer" or your score] Hope this will help you in giving a small hint regarding where your solution is going wrong. 
Added by:  Programming Club, IITK 
Date:  20171012 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 