Connected Components

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

N ≤ 1000, the number of vertices.
An adjacency matrix, N rows with N numbers (0/1).
The matrix will be symmetrical (it is undirected!).

Output

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

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 28, 2013

Problem Types: [Show] [Hide]

• Graph Theory

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)