Exercise 1: Build an Adjacency List 🔗

Your Task

Write a function build_adj_list(num_nodes, edges) that converts an edge list into an adjacency list.

The graph is directed — each edge [a, b] means there's an arrow from node a to node b.

Return the adjacency list as a dictionary mapping each node to its list of neighbors.

---

Examples

print(build_adj_list(4, [[0,1], [0,2], [1,3], [2,3]]))
# Output: {0: [1, 2], 1: [3], 2: [3], 3: []}

print(build_adj_list(3, [[0,1], [1,2], [2,0]]))
# Output: {0: [1], 1: [2], 2: [0]}

print(build_adj_list(3, []))
# Output: {0: [], 1: [], 2: []}

---

Expected Complexity

	Complexity
Time	O(V + E)
Space	O(V + E)

Where V is the number of nodes and E is the number of edges.

Why? We initialize V empty lists, then iterate through E edges.

---

Approach

1. Create a dictionary with an empty list for each node 0 to num_nodes - 1
2. For each edge [a, b], append b to the list at key a
3. Return the dictionary

Key insight: In a directed graph, edge [a, b] only adds b to a's list (not the reverse). For undirected graphs you'd add both directions.

---

Starter Code

def build_adj_list(num_nodes, edges):
    # Your code here
    pass

# Test your function:
print(build_adj_list(4, [[0,1], [0,2], [1,3], [2,3]]))
# Output: {0: [1, 2], 1: [3], 2: [3], 3: []}

print(build_adj_list(3, [[0,1], [1,2], [2,0]]))
# Output: {0: [1], 1: [2], 2: [0]}

print(build_adj_list(3, []))
# Output: {0: [], 1: [], 2: []}

print(build_adj_list(5, [[0,1], [0,2], [1,3], [2,3], [3,4]]))
# Output: {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: []}

---

Hints