Start learning free

LESSON 558 OF 667 · GRAPHS

Graph Valid Tree

Practice O((n + e)·α(n))

You get an undirected graph with n nodes, labeled 0 to n - 1. Its edges come as a vector edges. Each edges[i] = [ai, bi] joins nodes ai and bi.

Return true if the graph is a tree, or false if it isn't.

A graph is a tree when it is connected and has no cycle. Connected means a chain of edges leads from any node to any other. A cycle is a route that returns to its start without reusing an edge. So in a tree, there is exactly one route between any two nodes.

 

Example 1:

Input: n = 6, edges = [[2, 0], [2, 5], [5, 1], [5, 3], [4, 2]]
Output: true
Explanation: All six nodes are linked.
There is no cycle.
        2
      / | \
     0  5  4
       / \
      1   3

Example 2:

Input: n = 4, edges = [[0, 2], [2, 3], [3, 0]]
Output: false
Explanation: There are 3 edges, the right number for a tree of 4 nodes.
But the edges form the cycle 0 - 2 - 3 - 0.
And node 1 has no edge at all.

Example 3:

Input: n = 1, edges = []
Output: true
Explanation: A single node with no edges is a tree.

 

Constraints:

  • 1 to 100,000 nodes.
  • 0 to 100,000 edges.
  • Each edge joins two different nodes.
  • Every node in edges is from 0 to n - 1.
  • No edge is listed twice.

Note:

Your algorithm should run in O((n + e)·α(n)) time, nearly O(n + e), where e is the number of edges, and use O(n) extra space.

A tree with n nodes has exactly n - 1 edges. With that many edges, the graph is a tree exactly when no edge closes a cycle, because then every edge joins two separate groups and the n single nodes end up as one group. The tutorial checks the count first, then adds the edges one by one with union-find, as in Number of Connected Components in an Undirected Graph: an edge whose two nodes are already in the same group closes a cycle. With path halving and union by size, each step costs O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any n a computer can hold.

A DFS or BFS from node 0 that checks that every node is reached also works in O(n + e) once the count is right; on a graph this big, use a BFS or a DFS with its own stack, since a recursive DFS down a path of 105 nodes can run out of call stack.

STEP 1 OF 18
    Ctrl + Enter to check