Start learning free

LESSON 470 OF 536 · GRAPHS

Graph Valid Tree in Python: Edge Count and Union-Find

Practice O((n + e)·α(n)) Read the full explanation

You have a graph of n nodes, numbered from 0 to n - 1, and a list edges where edges[i] = [ai, bi] means that there is an undirected edge between nodes ai and bi.

The graph is a tree when it is connected (you can get from any node to any other by following edges) and has no cycle (no path of edges leads from a node back to itself without using an edge twice). Put another way, there is exactly one path between any two nodes.

Return True if the edges make the graph a valid tree, or False otherwise.

 

Example 1:

Input: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output: True
Explanation: Every node can be reached from node 0, and no edge closes a cycle:
        0
      / | \
     1  2  3
     |
     4

Example 2:

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output: False
Explanation: The edges 1 - 2, 2 - 3 and 1 - 3 form a cycle, so there are two paths from 1 to 3.

Example 3:

Input: n = 4, edges = [[0, 1], [1, 2], [2, 0]]
Output: False
Explanation: There are 3 edges for 4 nodes, the number a tree of 4 nodes has, but the edges
0 - 1, 1 - 2 and 2 - 0 form a cycle, and node 3 has no edge at all. Counting the edges is not enough.

 

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.

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 16
    Ctrl + Enter to check

    PYTHON · GRAPHS

    Graph Valid Tree in Python, explained

    Problem overview

    The method validTree receives n, the number of nodes (numbered 0 to n - 1), and a list edges of pairs. Each pair [a, b] is an undirected edge. The method returns True when the graph is a tree and False otherwise.

    A graph is a tree when it is connected, so you can get from any node to any other, and has no cycle. Equivalently, there is exactly one path between any two nodes.

    With n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]] the answer is True: every node is reachable from node 0 and no edge closes a loop. With edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] it is False, because the edges 1-2, 2-3 and 1-3 form a cycle. With n = 4 and edges = [[0, 1], [1, 2], [2, 0]] it is also False: there are 3 edges, which is the number a tree of 4 nodes has, but they form a cycle and node 3 is isolated.

    The statement asks for O((n + e) · α(n)) time, which is nearly O(n + e), and O(n) extra space, where e is the number of edges.

    Approach: count the edges, then look for a cycle

    A tree with n nodes has exactly n - 1 edges. That gives a quick first test. With fewer edges, some node is cut off from the rest. With more, some edge must close a cycle. So if len(edges) isn't n - 1, the answer is False right away.

    The count alone isn't enough, as the third example shows. But once the count is right, one condition remains: the graph is a tree exactly when no edge closes a cycle. The reason is that each edge that doesn't close a cycle joins two separate groups of nodes. After n - 1 such edges, the n single nodes have merged into one group, which means the graph is connected.

    To detect a cycle, the lesson uses union-find. It keeps the groups of connected nodes as small trees, where every node points to a parent and the root, the one node that is its own parent, names its group. Two nodes are in the same group exactly when they lead to the same root. When an edge joins two nodes that already share a root, they were already connected, so this edge adds a second path between them: a cycle.

    Two refinements keep the trees shallow. Union by size hangs the smaller tree under the larger one. Path halving shortens paths while searching for a root. Together they make each step cost O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any size of input a computer can hold.

    Here are the parent and size lists after each edge of the first example, n = 5:

    [0, 1] parent [0, 0, 2, 3, 4] size [2, 1, 1, 1, 1]
[0, 2] parent [0, 0, 0, 3, 4] size [3, 1, 1, 1, 1]
[0, 3] parent [0, 0, 0, 0, 4] size [4, 1, 1, 1, 1]
[1, 4] parent [0, 0, 0, 0, 0] size [5, 1, 1, 1, 1]

    All five nodes end up under root 0 and no edge was rejected. For the second example, the first three edges merge nodes 0 to 3 under root 0 in the same way. The fourth edge, [1, 3], finds both nodes under root 0, so the function returns False.

    A depth-first or breadth-first search from node 0 that checks every node was reached also works once the count is right. On large inputs it needs a loop with its own stack, because a recursive search down a path of 100,000 nodes can exceed Python's recursion limit.

    Step by step

    1. Check the edge count. If len(edges) != n - 1, return False.
    2. Create parent as list(range(n)). Every node starts as its own root, a group of one.
    3. Create size as n ones. For a root r, size[r] is the number of nodes in its group. Only the roots' entries are kept up to date.
    4. Loop over edges with edge. Each edge either merges two groups or closes a cycle.
    5. Find rootA with self.find(parent, edge[0]). The helper is written last, which keeps the loop short.
    6. Find rootB for edge[1] in the same way.
    7. Compare the roots. If rootA == rootB, the ends were already connected, so return False.
    8. Union by size. If size[rootA] < size[rootB], swap the two roots with a tuple assignment, so that rootA is the root of the larger group. A node moves one level deeper only when its group at least doubles in size, so no path to a root is longer than about log2(n) steps.
    9. Merge: set parent[rootB] = rootA, outside the short if, so that it runs every time.
    10. Add the sizes: size[rootA] += size[rootB]. The entry for rootB is never read again, because it is no longer a root.
    11. After the loop, return True. Every one of the n - 1 edges merged two groups, so the graph is connected and has no cycle.
    12. Write the method find in the class. It takes self, parent and a node x, and returns the root of x's group.
    13. Loop while parent[x] != x. The root is the only node that is its own parent. A loop needs no call stack, however long the walk is.
    14. Point x at its grandparent: parent[x] = parent[parent[x]]. This is path halving: each node passed skips one level.
    15. Move up: x = parent[x], which is now the old grandparent.
    16. Return x, the root.

    The solution in Python

    class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        parent = list(range(n))
        size = [1] * n
        for edge in edges:
            rootA = self.find(parent, edge[0])
            rootB = self.find(parent, edge[1])
            if rootA == rootB:
                return False
            if size[rootA] < size[rootB]:
                rootA, rootB = rootB, rootA
            parent[rootB] = rootA
            size[rootA] += size[rootB]
        return True

    def find(self, parent: List[int], x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    Python details worth a closer look:

    • list(range(n)) turns the range into the list [0, 1, ..., n - 1], where each node is its own parent.
    • Tuple assignment. rootA, rootB = rootB, rootA evaluates the right side first, so the two names swap without a temporary variable.
    • Lists are shared, not copied. find receives the same list object as validTree, so its changes to parent are seen by the caller. That is what makes path halving useful across calls.
    • Path halving in action. With parent = [0, 0, 1, 2, 3], a chain, find(parent, 4) returns 0 and leaves parent as [0, 0, 0, 2, 2]. Node 4 now points to 2, and node 2 to 0.
    • Iteration instead of recursion. A recursive find on a long chain could hit Python's default recursion limit. The while loop has no such limit.

    Complexity

    Time: O((n + e) · α(n)). Building the lists takes O(n). Because the edge count is checked first, the loop runs at most n - 1 times, each with two find calls costing O(α(n)) on average. That is nearly O(n + e).

    Space: O(n). The parent and size lists have n entries each.

    Edge cases and common mistakes

    • Only counting edges. n = 4 with [[0, 1], [1, 2], [2, 0]] has the right count and is not a tree. The cycle check catches it.
    • Only checking for cycles. Without the count, n = 3 with [[0, 1]] would have no cycle and return True, although node 2 is disconnected. The function returns False because the count 1 is not n - 1 = 2.
    • A single node. n = 1 with no edges is a tree: 0 == 1 - 1, the loop doesn't run, and the result is True. With n = 2 and no edges the count fails and the result is False.
    • Comparing the nodes instead of the roots. Edges [0, 1], [1, 2], [2, 0] never repeat a pair of nodes, yet the last one closes a cycle. Only the roots show it.
    • Updating size for the wrong root. After the swap, rootA is the larger group's root, so the sizes add into rootA.
    • Forgetting to return the root. If find returned the last parent[x] read instead of x after the loop, the roots compared would be wrong.

    Testing

    • n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]] gives True.
    • n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] gives False.
    • n = 4, edges = [[0, 1], [1, 2], [2, 0]] gives False.
    • n = 5, edges = [[0, 1], [1, 2], [2, 0], [3, 4]] gives False: right count, but a cycle and a separate pair.
    • n = 1, edges = [] gives True.
    • n = 2, edges = [] gives False.
    • n = 2, edges = [[0, 1]] gives True.
    • n = 4, edges = [[0, 1], [1, 2], [2, 3]] gives True.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free