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
varungpt: 2017-11-02 09:21:51

The problem I was facing was inbuilt sort() function sorts in dictionary order (e.g. 12 comes before 3) but we have to sort by numerical value.

pranaybaldev: 2017-11-01 22:04:18

Same as @varungpt and @abhas_bajpai. :/

abhas_bajpai: 2017-10-31 13:05:31

Same as @varungpt .I am using JAVA to write the code and my code is giving the correct output for the given test cases as well as many other random test cases which I checked by myself. But on submitting it shows AC for case 3 and WA for the rest.
Plz help.

Last edit: 2017-11-01 19:43:07
varungpt: 2017-10-31 12:33:31

I am getting correct answer for only case 3, but both the provided test cases are working fine and also what @ nikhilbl has suggested. Do anyone has any idea what might be the problem?

dmittal: 2017-10-31 08:06:55

@khemraj891289:i too am getting wrong answer in 2nd test case. did you find out what goes wrong.

khemraj891289: 2017-10-29 13:02:50

I got wrong answer for 2nd and 4th case. Is anyone suggest me sample test case for the same ?

Programming Club, IITK: 2017-10-29 11:31:54

@vijaygs : We have taken care of extra whitespaces. Also, the same code was used to generate the solution for the test case you see above and the hidden test cases. Format across all the testcases is same. I am skeptical that by only changing print statements , your score went from 30 to 100.

vijaygs: 2017-10-27 21:11:10

Please include some way to accept various formats of printing the final output. Just now, after spending hours to figure out the bug in my code, I finally replaced 'print' statement in python with 'stdout.write'. And, right away, the score shot up from 30 to 100. A bug of this sort, which is not even in our control, is very difficult to guess and we spend hours just on trivial points. This is not the first time it is happening. In the last assignment, exactly the same issue happened, but at least, in that case, the code didn't function for any of the test cases. This time, it worked for a few and didn't for others. It was very difficult to guess the bug.

Last edit: 2017-10-27 21:11:35
Programming Club, IITK: 2017-10-27 09:39:33

For people asking for more test cases: you can generate your own test cases with a program. You only need to write a program that generates random graphs. And then you can test your solution on zillions of test cases!

Programming Club, IITK: 2017-10-26 14:32:36

@ashutoshs25: Please check your code carefully for all instances of malloc/free/array access. The program abort signal is most probably due to memory allocation/access/release related issue.


Added by:Programming Club, IITK
Date:2017-10-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All