Trace lab in Graph Representations and Traversal

Mission

Report the degree of every vertex.

Learning outcome: Trace vertex degrees in an undirected graph

Correctness contract

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

Required technique: Increment the degree of both endpoints for every undirected edge.

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

Input and output

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

Output: Print one index:count token per vertex in ascending index order, separated by single spaces. 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: Increment the degree of both endpoints for every undirected edge.
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

4 3 0 1 1 2 1 3

Sample output

0:1 1:3 2:1 3:1

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Every undirected edge increases the degree of both endpoints once. Input `4 3 0 1 1 2 1 3` therefore produces `0:1 1:3 2:1 3:1`.

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.