Training Site
Sideways banner

Connected Components

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds

Read in a undirected graph which has been described as a list of edges and then output the connected components of the graph.

An extra "rule" so that your results can be easily compared:
At any point if there is a choice of which vertex to visit, visit them in ascending numerical order
Eg: if a vertex's neighbours are 5,2,7 and 3 process them in the order 2, 3, 5 then 7.

Input format

Each vertex will be represented as a number from 0 to n-1 for n vertices.
The first line of input will state how many vertices are in the graph
Each subsequent line will consist of pairs of numbers each describing an edge. The first number in the pair describes the vertex from where the edge originates and the second number states the vertex where the edge leads to. The list will end in a -1 -1 pair which is not to be included as an edge.

Output format

Output on separate lines the vertices, (sorted and separated by spaces) in each of the connected components of the graph. Label the components numerically starting at 1.

  • Sample Input 1

    3 1
    5 0
    2 0
    1 4
    2 5
    4 3
    -1 -1

    Sample Output 1

    1: 0 2 5
    2: 1 3 4