Implementation lab in Graph Representations and Traversal

Mission

Build a directed adjacency matrix and print compact rows.

Learning outcome: Implement an adjacency matrix

Correctness contract

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

Required technique: Allocate a V by V matrix and set only the directed from-to entries supplied.

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

Input and output

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

Output: Print one compact 0/1 row per vertex, 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: Allocate a V by V matrix and set only the directed from-to entries supplied.
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

3 2 0 1 1 2

Sample output

010 001 000

Why the sample works: Visible walkthrough for the ordinary non-trivial path. Each directed edge sets its from-row, to-column cell to one; all other cells remain zero. Input `3 2 0 1 1 2` therefore produces `010 001 000`.

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.