Connected Components in an Undirected Graph

You are given an undirected graph (G=(V,E)) with (n) nodes labeled from 1 to (n) and (m) edges. The graph may be disconnected, and some nodes might be isolated. Your task is to find all connected components (clusters) in the graph. For each connected component, output the nodes in ascending order. Finally, print the components sorted by the smallest node in each component.

Example: Consider the graph with 6 nodes and 4 edges:

• Edge between 1 and 2
• Edge between 1 and 3
• Edge between 2 and 4
• Edge between 5 and 6

This graph has two connected components: one containing nodes 1, 2, 3, 4 and the other containing nodes 5, 6.

Note: Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the graph.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(n\) and \(m\), where \(n\) is the number of nodes and \(m\) is the number of edges.
• The next \(m\) lines each contain two integers \(u\) and \(v\), representing an undirected edge between nodes \(u\) and \(v\).

Nodes are numbered from 1 to (n). If (n=0), the input will contain just one line, and no output should be produced.

outputFormat

The output is printed to standard output (stdout). For each connected component, print a line containing the nodes in that component in ascending order, with a single space between numbers. The connected components should be printed in the order of their smallest element (also in ascending order). If there are no nodes (i.e. (n=0)), do not print anything.## sample

0 0