Các bài nộp | Làm tốt nhất | Về danh sách bài |

## 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 order-id(v) = min{label(v_{i}) | v_{i} is part of v in V_{SCC}}

Vertex v in V_{SCC} 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 i^{th} line (1^{st} , 2^{nd} ...) 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:

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 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 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

Được gửi lên bởi: | Programming Club, IITK |

Ngày: | 2017-10-12 |

Thời gian chạy: | 1s |

Giới hạn mã nguồn: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Ngôn ngữ cho phép: | C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3 |