Is the Network a Tree

EasyGraphs

Problem

You are given n devices numbered 0 to n - 1 and a list of undirected links, each [a, b] with a ≠ b.

Return true if the links form a tree: every device can reach every other one, and there is no loop. Otherwise return false.

Example 1

Input:
n = 5, links = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output:
true

Example 2

Input:
n = 5, links = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output:
false

1 → 2 → 3 → 1 is a loop.

Example 3

Input:
n = 4, links = [[0, 1], [2, 3]]
Output:
false

Two separate pieces.

Constraints

  • 1 ≤ n ≤ 10^4
  • 0 ≤ links.length ≤ 2·10^4
  • 0 ≤ a, b < n, a ≠ b

Hint

Show the first hint

How many links must a tree on n devices have?

Walkthrough

How to approach it

01Clarify before coding

  • Is a single device with no links a tree? Yes.
  • Can a link repeat? Yes, and a repeated link is a loop.
  • Do I need to report why it fails? No, just true or false.

02Brute force

Run a BFS to check that everything is reachable, and separately run a cycle-detecting DFS that tracks parents.

Cost: O(n + m), already linear, but two traversals and fiddly parent tracking for repeated links.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.