Graph problems usually hand you a list of edges, but BFS, DFS and friends want to ask "who are the neighbours of node u?" in O(1). The adjacency list answers exactly that question.
Given n nodes numbered 0 .. n-1 and a list of undirected edges edges (each [u, v]), return the adjacency list: a list adj of length n where adj[u] is the list of neighbours of u. Neighbours may be listed in any order.
Examples
Input: n = 4, edges = [[0, 1], [1, 2], [2, 3]]
Output: [[1], [0, 2], [1, 3], [2]]
Input: n = 3, edges = []
Output: [[], [], []]
Constraints
1 <= n <= 1000,0 <= len(edges) <= 5000- No duplicate edges and no self-loops
- Target: O(n + E) time
Goals
- Convert an edge list into an adjacency list, the representation almost every graph algorithm starts from
- Remember that an undirected edge must be recorded in both directions
- Create a list of n independent empty lists without the [[]] * n aliasing bug