Valid Spanning Tree

Difficulty: Easy · Topic: Minimum spanning trees

Given n nodes labeled 0..n-1 and undirected edges [u, v], return True if those edges form a spanning tree: all nodes are connected and there is no cycle.

Examples

valid_spanning_tree(5, [[0,1],[0,2],[0,3],[1,4]])
→ true

valid_spanning_tree(5, [[0,1],[1,2],[2,0],[3,4]])
→ false

There is a cycle among 0,1,2 and node 3/4 are separate.

valid_spanning_tree(1, [])
→ true

Target complexity: time O(E alpha(V)), space O(V)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.