Who is next to whom
Turn a list of edges into a list of neighbours for every node. About 10 minutes.
Give every node its own contact list
A list of edges is like a pile of receipts: to answer "who lives next to house 2?" you would have to read every single one. So reorganise once. Give each house its own contact list, then read each edge and write it into both houses' lists.
After that, the answer to "who lives next door?" is just a look at that house's list, instantly.
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
for neighbours in adj:
neighbours.sort()
return adj- adj[0]
- []
- adj[1]
- []
- adj[2]
- []
- adj[3]
- []
Four houses and no lanes read yet. Every house gets an empty contact list, even one that might stay empty.
The classic slip
The most common bug here is writing the edge into only one of the two lists. Your code still runs, but now house v doesn't know house u exists, and every search that starts from v will miss it.
It is like giving someone your number but never saving theirs. Step through the picture below and watch each edge land in two lists.
n = 3, edges = [[1, 2]]. What is adj[0]?
- A[] (no neighbours)
- BNode 0 is left out of the list
- C[2]
Show the answer
[] (no neighbours). No lane touches house 0, so its list stays empty. It still exists, though, so adj[0] works.
Who is next to whom
A small town has n houses numbered 0 to n - 1, and edges lists the lanes: [u, v] means a lane joins house u and house v, and it can be walked either way. Return, for every house in order, the list of houses it has a direct lane to, each list sorted from smallest to largest.
n = 4, edges = [[0, 1], [0, 2], [2, 3]] → [[1, 2], [0], [0, 3], [2]]
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · 0 ≤ u, v < n · no edge joins a node to itself and no edge appears twice