Graph Contest 2 P1 - Connected Components

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 16M
Problem type

Given an undirected graph (as an adjacency matrix, of course) output all its connected components.
You may output the components in any order, but for each component output the vertices in increasing order.

Input Specification

N \le 1\,000, the number of vertices.
An adjacency matrix, N rows with N numbers (0 or 1).
The matrix will be symmetrical (it is undirected!).

Output Specification

The components, one per line.
Each line should be in sorted order.

Sample Input

5
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0

Sample Output

1
2
3 4 5

Comments


  • 18
    Plasmatic  commented on Sept. 23, 2020, 2:48 a.m. ← edited

    It appears that the components themselves have to be outputted in the order of their smallest elements, as opposed to in any order (like the problem statement says). (i.e. if the components were 1 5 6 7, 8 9, 3, 2 4 the output would be

    1 5 6 7
2 4
3
8 9

    )