Loading
Loading
A campus network links n buildings, numbered 1 to n, with exactly n two-way cables. With one cable fewer it would be a tree — every building reachable from every other with no loops — but an installer laid one cable too many.
cables[i] = [a, b] is the i-th cable laid. Return a cable that can be removed so the network becomes a tree again. Several cables may qualify; return the one that was laid last, written exactly as it appears in the input.
cables = [[1,2],[2,3],[3,4],[1,4],[1,5]][1,2] [2,3] [3,4]each joins two separate groups[1,4]1 and 4 are already connected via 2 and 3 — this closes a looploop 1-2-3-4removing any of its four cables works; [1,4] was laid last[1,4]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 2 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 1 | 3 |
Example 2
| 0 | 1 |
|---|
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 2 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 1 | 3 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 2 |
| 1 | 2 | 3 |
|---|
| 2 | 3 | 4 |
|---|
| 3 | 1 | 4 |
|---|
| 4 | 1 | 5 |
|---|
Example 3
| 0 | 3 | 4 |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 4 |
| 3 | 1 | 3 |
| 4 | 2 | 5 |
| 5 | 5 | 6 |