Clone and Relabel a Network
MediumGraphs
Problem
An undirected network is given as adjacency lists: adj[i] lists the neighbours of node i, and whenever j appears in adj[i], i appears in adj[j].
Copy the part of the network reachable from start into a fresh structure with new labels. Labels are handed out in breadth-first discovery order: start gets 0, and when a node is processed its neighbours are examined in the order they appear in its list, each previously unseen neighbour receiving the next free label.
Return the adjacency lists of the copy: entry k lists the new labels of the neighbours of the node labelled k, in the same order as in the original list.
Example 1
- Input:
- adj = [[2], [3], [0, 3], [1, 2]], start = 3
- Output:
- [[1, 2], [0], [3, 0], [2]]
3 → 0; its neighbours 1 → 1 and 2 → 2; node 1 adds nothing new; node 2 discovers 0 → 3. Old 2's list [0, 3] becomes [3, 0].
Example 2
- Input:
- adj = [[1, 2], [0, 3], [0], [1]], start = 0
- Output:
- [[1, 2], [0, 3], [0], [1]]
BFS from 0 happens to keep every label.
Example 3
- Input:
- adj = [[], [2], [1]], start = 0
- Output:
- [[]]
Node 0 is isolated; only it is copied.
Constraints
- 1 ≤ adj.length ≤ 10^4
- Total neighbour entries ≤ 4·10^4
- No self-loops or repeated neighbours.
- 0 ≤ start < adj.length
Hint
Show the first hint
Cloning a graph always needs one key structure: a way to go from an original node to its copy.
Walkthrough
How to approach it
01Clarify before coding
- Are unreachable nodes copied? No, only the component containing start.
- Does neighbour order matter? Yes: it drives the labelling and must be preserved in the output lists.
- Is the graph undirected? Yes, so every neighbour of a copied node is itself copied.
02Brute force
Run BFS to collect the labels, then for each copied node search the discovery list linearly to translate every neighbour.
Cost: O(n · m): each translation is a linear search, about 4·10^8 steps at the limits.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.