DFS Traversal Problem Statement

Given an undirected and disconnected graph G(V, E), where V is the number of vertices and E is the number of edges, the connections between vertices are provided in the 'GRAPH' matrix. Each element of the matrix denotes an edge between two vertices.

Input:

The first line of input contains two integers, V and E, separated by a space. Following this line are E lines, each containing two space-separated integers a and b, indicating an undirected edge between vertices a and b.

Output:

The first line should print the number of connected components in the graph. For each connected component, list its vertices in ascending order, separated by spaces. Each connected component should be printed on a new line, starting with the component that has the smallest vertex number.

Example:

Input:

5 3 0 1 1 2 3 4

Output:

2 0 1 2 3 4

Explanation:

The graph has 5 vertices and 3 edges, forming two connected components: one with vertices 0, 1, and 2; and another with vertices 3 and 4.

Constraints:

2

Question

DFS Traversal Problem Statement

Given an undirected and disconnected graph G(V, E), where V is the number of vertices and E is the number of edges, the connections between vertices are provided in the 'GRAPH' matrix. Each element of the matrix denotes an edge between two vertices.

Input:

The first line of input contains two integers, V and E, separated by a space.
Following this line are E lines, each containing two space-separated integers a and b, indicating an undirected edge between vertices a and b.

Output:

The first line should print the number of connected components in the graph.
For each connected component, list its vertices in ascending order, separated by spaces.
Each connected component should be printed on a new line, starting with the component that has the smallest vertex number.

Example:

Input:

Output:

2
0 1 2
3 4

Explanation:

The graph has 5 vertices and 3 edges, forming two connected components: one with vertices 0, 1, and 2; and another with vertices 3 and 4.

Constraints:

2 <= V <= 10^3
1 <= E <= 5 * 10^3
Time Limit: 1 sec

Note

The graph might not be connected, which means there may be multiple components.

Accepted Answer

DFS traversal problem on an undirected and disconnected graph to find connected components.

Use Depth First Search (DFS) algorithm to traverse the graph and find connected components.
Maintain a visited array to keep track of visited vertices.
For each unvisited vertex, perform DFS to explore all connected vertices and form a connected component.
Repeat the process until all vertices are visited and print the connected components.
Handle disconnected components by starting DFS from unvisited vertices.
Example: For input 5 3, 0 1, 1 2, 3 4, the output should be 2, 0 1 2, 3 4.

DFS Traversal Problem Statement

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

Note

Cognizant Software Analyst interview questions & answers

Popular interview questions of Software Analyst