Edges Form a Single Tree
Problem
You are given n nodes labelled 0 to n - 1 and a list of undirected edges. Return whether the edges form exactly one tree: every node is connected to every other, and there is no cycle.
Examples
Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: TrueInput: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: False
Why: 1, 2 and 3 form a cycleInput: n = 4, edges = [[0, 1], [2, 3]]
Output: False
Why: edge case, no cycle, but the graph is in two piecesHints
0 / 3
A tree on n nodes has exactly n - 1 edges. That count alone rules out many inputs.
With exactly n - 1 edges, a graph is a tree precisely when it has no cycle, because an acyclic graph with that many edges is automatically connected.
Check the edge count first. Then union the two ends of every edge in a disjoint set, and if both ends already share a root, that edge closes a cycle, so the answer is False.
Solution
Two facts about trees do all the work. A tree on n nodes has exactly n - 1 edges, and a graph with n - 1 edges and no cycle is always connected, since each edge that joins two different components reduces the component count by one, from n down to exactly 1. So after the count check the only question is whether some edge closes a cycle, which is precisely what a disjoint set answers: an edge whose two ends already have the same root connects nodes that were connected before. Path halving keeps the trees shallow. Time is O(n · α(n)), effectively linear, and space is O(n).
def is_single_tree(n, edges):
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra == rb: # already connected: this edge closes a cycle
return False
parent[ra] = rb
return True
print(is_single_tree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])) # -> True
print(is_single_tree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) # -> False
print(is_single_tree(4, [[0, 1], [2, 3]])) # -> FalseStuck on the idea rather than the code? Components & Cycles covers it.