Challenge lab in Graph Representations and Traversal

Mission

Count connected components in an undirected graph.

Learning outcome: Count connected components

Correctness contract

Invariant: A vertex is marked when discovered so every reachable vertex is processed once.

Required technique: Scan every vertex and start one traversal from each still-unvisited vertex.

Complexity target: time O(V+E); space O(V+E).

Input and output

Input: V and E followed by E vertex pairs. Whitespace may be spaces or line breaks.

Output: Print the single exact numeric result with no label. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• V is positive and every vertex index is in the range 0 through V - 1.
• The declared edge count exactly matches the supplied pairs.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Scan every vertex and start one traversal from each still-unvisited vertex.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 2 0 1 3 4

Sample output

3

Why the sample works: Visible walkthrough for the ordinary non-trivial path. A new traversal starts at every still-unvisited vertex, including isolated vertices. Input `5 2 0 1 3 4` therefore produces `3`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Trace the smallest non-trivial input and write the structure state after the operation before coding the loop.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.