Do the Links Form a Tree

Medium

There are node_count nodes numbered 0 to node_count - 1 and a list of undirected links links, where links[i] = [a, b] connects nodes a and b. Return True if the links form a tree: every node can reach every other node and there is no cycle anywhere. Otherwise return False.

Example 1

node_count=4, links=[[0, 1], [1, 2], [1, 3]] → True

Node 1 is linked to all the others, every node is reachable and there are no cycles, so this is a tree.

Example 2

node_count=4, links=[[0, 1], [2, 3]] → False

There are two separate parts: you cannot get from 0 to 2.

Example 3

node_count=3, links=[[0, 1], [1, 2], [2, 0]] → False

All nodes are connected, but the three links form a cycle.

Constraints

1 ≤ node_count ≤ 2000
0 ≤ len(links) ≤ 5000
links[i] = [a, b], 0 ≤ a, b < node_count, a ≠ b
Each pair of nodes is linked at most once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Graph

Similar problems

Isolated Groups in a Network Medium Ratio Chain Queries Medium Clusters of Linked Servers Medium The Extra Cable Medium Split Into Two Teams Medium

Input

node_count=4, links=[[0, 1], [1, 2], [1, 3]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.