367. Size of the Largest Component
Core1000 ms256 MBSolved by 0%
Print the number of vertices in the largest connected component.
Problem 363 counted how many components there are. This one measures them. The traversal is the same; the only addition is a counter that increases once per vertex removed from the stack, and a running maximum across the starts.
Every vertex is in exactly one component, so the sizes add up to n. A graph
with no edges at all has n components of size 1, and the answer is 1.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the size of the largest component.
Input5 4
1 2
2 3
3 1
4 5
Output3
Notehas a triangle of three and a pair, so the larger one wins
Input4 3
1 2
2 3
3 4
Output4
Noteis one component holding every vertex
Input3 0
Output1
Notehas no edges, so every component is a single vertex
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution