Graph Valid Tree

Q: What is the time complexity of Graph Valid Tree?

O(n + m) with a depth-first search, where m is the number of edges, and O(n + m α(n)) with union-find. Both check the edge count first, so a graph with the wrong count is rejected before any search.

MediumUnion-find Graphs

+10

You get n nodes, numbered from 0 to n-1, and a list edges of undirected edges. Each pair [a, b] joins node a and node b.

Return true if the edges make all n nodes into one tree: every node can reach every other node, and there is no cycle. Return false otherwise.

Function

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: the number of nodes, numbered 0 to n-1
edgesinteger-2d-array: the undirected edges, each a pair [a, b]
Returnsboolean: true if the edges join all n nodes into one tree, false otherwise

Constraints

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] with 0 ≤ a, b ≤ n-1 and a ≠ b
No edge appears twice, in either direction.

Examples

Input: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: true
Explanation: Node 0 links to nodes 1, 2 and 3, and node 4 hangs off node 1. Four edges join all five nodes with no loop, so this is a tree.

Input: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: false
Explanation: The edges [1, 2], [2, 3] and [1, 3] form the loop 1, 2, 3, 1. Five edges on five nodes are one more than a tree can have.

Input: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Output: false
Explanation: There are 3 edges, which is n-1, but they form the loop 0, 1, 2, 0, and node 3 has no edge at all.

Follow-up

When the graph is not a tree, how many edges must you remove, and how many add, to make it one? Can you count both in one pass?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A tree is connected and has no cycle. With exactly n-1 edges these are one condition: such a graph is connected exactly when it has no cycle. So check the edge count first, then either search once for connectivity, or let union-find catch an edge that joins two nodes already linked.

Search for a path before every edge

Correct, but does not finish on the largest tests

Intuition

Add the edges one at a time. Before adding [u, v], search from u over the edges added so far. If v is reachable, the new edge is a second route between them and closes a cycle, as [1, 3] does in the second example. If no edge closes a cycle, the graph is a forest, and a last search from node 0 tells whether it is one tree.

Each check searches the whole graph so far. On a path of 5001 nodes whose edges arrive in order, the searches visit 1 + 2 + ... + 5000 nodes, about 12.5 million.

Algorithm

Start with an empty adjacency list per node.
For each edge [u, v], search from u over the edges added so far. If it reaches v, return false.
Otherwise add the edge to the lists of both ends.
At the end, return whether a search from node 0 reaches all n nodes.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Count the edges, then search once

Intuition

Start from n separate nodes and add the edges one by one. Each edge either joins two groups, leaving one group fewer, or lands inside a group and closes a cycle. Reaching one group takes n-1 joins. So fewer than n-1 edges cannot connect the graph, and more must close a cycle: the second example, 5 edges on 5 nodes, fails on the count alone.

With exactly n-1 edges, the graph ends as one group only if every edge was a join, that is, only if no edge closed a cycle. So once the count is right, check connectivity alone: one search from node 0 must reach all n nodes. In the third example it reaches only 0, 1 and 2. With m = n-1, the lists and the search cost O(n).

Algorithm

If edges.length is not n-1, return false.
Build an adjacency list, storing each edge under both of its ends.
Push node 0 on a stack and mark it seen.
Pop nodes and push every neighbour not seen yet, marking and counting it as you push.
Return whether the count equals n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Count the edges and union-find

Intuition

Union-find answers the cycle question for each edge without a search. Every node starts as its own group. For an edge [u, v], find the root of each end. Different roots: the edge joins two pieces, so merge them. Same root: u and v are already linked and the edge closes a cycle. With n-1 edges that all merge, the n groups end as one: a tree.

Two rules keep the parent chains short. A merge attaches the smaller group's root under the larger one's, so with 10^4 nodes no chain passes 13 steps. During a find, point each node you pass at its grandparent. Together they make m operations cost O(m α(n)), where α, the inverse Ackermann function, is at most 4 here. Space is O(n).

Algorithm

If edges.length is not n-1, return false.
Set parent[x] = x and a group size of 1 for every node.
For each edge [u, v], follow parents from u and from v to their roots, pointing each node you pass at its grandparent.
Equal roots: return false.
Different roots: attach the smaller group's root to the other and add its size.
If every edge merged two groups, return true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

Pitfalls and edge cases

Checking only for a cycle. Three separate edges on six nodes have no cycle, yet they form three pieces.
Checking only the edge count. The third example has n-1 edges, but the loop 0, 1, 2 uses up the edge node 3 needed.
Storing each edge under one end only. [1, 0] links nodes 0 and 1 too, and the search from node 0 misses node 1.
A depth-first cycle test that does not skip the parent. Every edge leads straight back to the node you came from, so "met a visited neighbour" fires on every tree.
Recursing on a long path. A line of 5001 nodes goes 5000 calls deep, past Python's default limit of 1000; use an explicit stack.

Frequently asked questions3

What is the time complexity of Graph Valid Tree?

O(n + m) with a depth-first search, where m is the number of edges, and O(n + m α(n)) with union-find. Both check the edge count first, so a graph with the wrong count is rejected before any search.

Why does a tree with n nodes have n-1 edges?

Grow the tree from one node and add the others one at a time. Each new node arrives with exactly one edge: with none it would be cut off, and with two it would close a cycle. So n nodes need n-1 edges.

How do you detect a cycle in an undirected graph?

With union-find, an edge whose two ends already share a root closes a cycle. With a depth-first search, a cycle is a visited neighbour other than the node you arrived from, so you track each node's parent. Union-find needs neither the parent nor an adjacency list.

def validTree(n, edges):
    # Write code here

Test #1

Test #2

Test #3

Arguments

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Expected Output

true

Graph Valid Tree

Function

Constraints

Examples

Hints

Solution

Search for a path before every edge

Count the edges, then search once

Count the edges and union-find

Pitfalls and edge cases

Frequently asked questions3

Similar problems