C++UCS301
Complexity Lab C++ Setup Visualizer
Practice arena
C++17·2 s·128 MB
GraphsFoundation

Count components

Count connected components in an undirected graph whose vertices are numbered 0 through n-1.

Input

  • — The first line contains T.
  • — Each case starts with n and m, followed by m undirected edges u v.

Output

Print the component count for each graph.

Technique

repeated BFS or DFS

Target

O(V + E)

Constraints & sample
  • 1 ≤ n ≤ 200,000
  • 0 ≤ m ≤ 300,000
  • No edge endpoint is outside [0, n)

Sample input

2
5 3
0 1
1 2
3 4
4 0

Expected output

2
4
Review the concept

Before you submit

  • Test the smallest valid input and one awkward edge case.
  • Keep the solution within O(V + E).
  • Match spacing and line breaks exactly before checking 7 hidden cases.
main.cpp
Draft saved locally · 472 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17

Visible testcases

Editable and stored only in this browser. Hidden judge cases never change.

Checking your session…

Run checks Sample · Submit checks 7 hidden cases

Run the sample first, then send your solution through 7 hidden cases.

Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.