Last Updated: 29 Sep, 2025

Significant Connected Components

Hard
Asked in company
Goldman Sachs

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.


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.