Tree or Not — Solution & Editorial

Back to the Problem

A tree on N nodes has exactly N−1 edges AND is connected — check both (either alone is insufficient).

Complexity: O(N + M)

Watch out: N−1 edges without connectivity means a cycle plus an isolated part — count components too.