IITKESO207A_3P_1 - Strongly connected components

no tags 

Given a digraph G = (V, E), print the strongly connected component graph GSCC = (VSCC, ESCC).

Labeling of vertices in VSCC should be done as follows:

For vertex v in VSCC , let us define order-id(v) = min{label(vi) | vi is part of v in VSCC}

Vertex v in VSCC with lowest value of order-id(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 ith line (1st , 2nd ...)  corresponds to the adjacency list of node numbered i-1 (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:


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 order-ids 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 GSCC. Verify the same in the following diagram:

Explanation of example

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
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: 2017-10-23 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.
Please provide us one more test cases to check our code!

Programming Club, IITK: 2017-10-23 06:48:07

@mkrishna1: No. It doesn't matter. You can always sort if you need to. Data sets are small.

mkrishna1: 2017-10-22 18:07:17

Are adjacency lists sorted in input?

Programming Club, IITK: 2017-10-20 20:48:46

@nikhilbl: No. All redundant multiple edges should be dropped. All self-loops should be dropped.

nikhilbl: 2017-10-20 14:58:14

Last edit: 2017-10-20 14:59:34
nikhilbl: 2017-10-20 14:37:44

Can one strongly connected component have multiple edges to another SCC?

Programming Club, IITK: 2017-10-18 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: 2017-10-18 09:55:32
Programming Club, IITK: 2017-10-18 09:41:52

@sronin: New line at the end does not matter, we ignore the extra whitespaces

sronin: 2017-10-18 08:30:45

is there a new line in the end?

Programming Club, IITK: 2017-10-16 10:33:10

Just to let you know guys: There are total 10 test cases. Test case #1-6 are small cases where n<=100 and test cases #7-10 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:2017-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All