A network team wants to know how short the tightest loop of cables is, because short loops cause broadcast storms. Devices are numbered 0 to n - 1, and cables[i] = [a, b] connects a and b (both ways).
Write shortestLoop(n, cables) that returns the number of cables in the shortest loop: a path that starts and ends at the same device, uses at least 3 cables, and never repeats a cable or a device (other than returning to the start). Return -1 if the network has no loop.
No cable is listed twice, and no cable connects a device to itself.
Input: n = 6, cables = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,2]] Output: 3
The triangle 0-1-2 uses 3 cables. The loop 2-3-4-5 uses 4.
Input: n = 4, cables = [[0,1],[1,2],[1,3]] Output: -1
These cables form a tree, so there is no loop.
2 <= n <= 3000 <= cables.length <= 20000 <= a, b < n, a !== bRun tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #414 Shortest Loop in a Network. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.