A data centre has n machines labelled 0 .. n - 1, and a list of cables: [a, b] joins machines a and b in both directions. The network team wants the layout to be a tree: every machine can reach every other one, and there is no loop, i.e. exactly one route between any two machines.
Write is_single_tree(n, cables) -> bool that returns True if the cables form such a tree, and False otherwise.
is_single_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) # True
is_single_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) # False (loop 1-2-3-1)
is_single_tree(4, [[0, 1], [2, 3]]) # False (two separate groups)
is_single_tree(1, []) # True
Constraints:
1 <= n <= 2 * 10^5and0 <= len(cables) <= 2 * 10^5.0 <= a, b < nanda != b. The same pair can appear more than once (two cables between the same machines form a loop).
Aim for close to O(n + m) time, where m = len(cables). The tests include an 80,000-machine chain, so a recursive search will hit Python's recursion limit.
Show hint
Add the cables one by one while tracking which machines are already connected. A cable between two machines that are already connected closes a loop; and if nothing ever closes a loop, the machines are all connected exactly when the number of cables is n - 1.