Significant Connected Components

Hard

0/120

0 upvote

Asked in company

Problem statement

You are given an undirected graph represented by a list of edges. Your task is to analyze the connectivity of this graph.

First, identify all the connected components. A connected component is a subgraph where any two vertices are connected to each other by a path, and which is connected to no additional vertices in the supergraph.

After finding all connected components, you must filter them according to a rule: only consider components that have 2 or more nodes.

From this filtered list of significant components, find the size (number of nodes) of the smallest component and the size of the largest component.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'E', the number of edges.

The next 'E' lines each contain two space-separated integers, u and v, representing a bi-directional edge between node u and v.

Output Format:

Print a single line with two space-separated integers: the size of the smallest significant component followed by the size of the largest significant component.

Note:

The node numbers in the input might not be contiguous or start from 0. The set of all unique node numbers from the edges defines the vertices of the graph.

"Significant" components are those with 2 or more nodes. Single-node components are ignored.

If there are fewer than two significant components, the smallest and largest size will be the same.

Sample Input 1:

Sample Output 1:

2 4

Explanation for Sample 1:

The edges define the following components:
- A component connecting `{1, 6, 2, 7}`. Size = 4.
- A component connecting `{3, 8}`. Size = 2.
- A component connecting `{4, 9}`. Size = 2.
The sizes of the components with 2 or more nodes are {4, 2, 2}.
The smallest of these sizes is 2, and the largest is 4.

Sample Input 2:

Sample Output 2:

2 2

Explanation for Sample 2:

There are three components: `{1, 2}`, `{3, 4}`, and `{5, 6}`. All have a size of 2.
The smallest size is 2, and the largest size is also 2.

Expected Time Complexity:

The expected time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Constraints:

1 <= E <= 10^5
1 <= u, v <= 2*E

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Significant Connected Components

Console