377. Create a Graph and Print Its Adjacency List

Given an undirected graph with n vertices (0-indexed) and m edges, build its adjacency list and print it: one line per vertex from 0 to n-1, each line listing that vertex's neighbors in ascending order, space-separated (print an empty line for a vertex with no neighbors).

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge. Output: Print n lines, one per vertex from 0 to n-1, each listing that vertex's neighbors in ascending order space-separated (an empty line for a vertex with no neighbors).

1 <= n <= 10^5

A vertex with ZERO edges still needs its OWN (empty) printed line - skipping it would shift every subsequent vertex's output line up by one, silently corrupting the expected output format.

Build and print the adjacency list representation of a graph from its edge list. Brute force: For every vertex, scan the ENTIRE edge list directly checking which edges touch it - this costs O(n * m), unnecessary when a single pass over the edges can build every vertex's list directly. Optimised: A single pass over the edge list, appending each endpoint to the OTHER's neighbor list as encountered, builds the complete adjacency list representation in linear time - no need to re-scan the edge list once per vertex.

Store all m edges as a flat list of (u, v) pairs. To print vertex i's neighbors, scan the entire edge list looking for edges touching i, collect the matches, and sort them ascending before printing. This avoids the O(n^2) matrix memory of the brute approach and only uses O(n + m) space, but repeating a full scan of all m edges for every one of the n vertices makes the printing step costly when both n and m are large. Time: O(n*m) Space: O(n + m)

Allocate an n x n matrix of booleans initialized to false, and for every input edge (u, v) set matrix[u][v] and matrix[v][u] to true. To print the adjacency list, for every vertex i scan its entire row from 0 to n-1 and print every j where matrix[i][j] is true (which is already ascending order for free). This is simple and correct but wastes O(n^2) memory and time regardless of how sparse the actual graph is, which is prohibitive once n approaches 10^5. Time: O(n^2) Space: O(n^2)

Allocate an array of n empty dynamic lists, one per vertex. For each input edge (u, v), append v to adj[u]'s list and u to adj[v]'s list directly - O(1) work per edge, O(m) total. Then sort each vertex's own (typically short) neighbor list ascending before printing it. Because each vertex only ever touches its own neighbor list rather than scanning every edge or every other vertex, both construction and printing scale with the actual size of the graph instead of n^2 or n*m. Time: O(n + m log m) Space: O(n + m)

1. Read all m edges first. 2. For each edge, add BOTH endpoints to EACH OTHER's neighbor list, since the graph is undirected. 3. Sort each vertex's neighbor list before printing, so the order is deterministic; a vertex with zero edges still gets its own (empty) printed line.

Time: O(n + m log(avg degree)) - O(m) to build the lists, plus sorting each vertex's own neighbor list (which together sum to O(m log(avg degree)) in the worst case). Space: O(n + m), for the adjacency list structure itself.

a vertex with zero neighbors (must still print an empty line), duplicate edges between the same pair of vertices, and n at its maximum of 10^5 to confirm the approach runs efficiently.

Be ready to mention that this is the FOUNDATIONAL data structure representation underlying nearly every other graph algorithm in this category - building it correctly and efficiently is a prerequisite skill for BFS, DFS, Dijkstra, and more.