Start learning free

LESSON 477 OF 543 · GRAPHS

Graph Valid Tree in Rust: Union-Find with Path Halving

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

You have a graph of n nodes, numbered from 0 to n - 1, and an array 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

    RUST · GRAPHS

    Graph Valid Tree in Rust, explained

    Problem overview

    The function valid_tree receives n, the number of nodes numbered 0 to n - 1, and edges, a vector of pairs where each pair is an undirected edge. It returns true when the edges make the graph a tree. A tree is connected (you can get from any node to any other) and has no cycle. Put another way, there is exactly one path between any two nodes.

    For n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]] the answer is true: every node can be reached from node 0, and no edge closes a cycle. For 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. For n = 4 and edges = [[0, 1], [1, 2], [2, 0]] it is also false: the count of 3 edges is right for 4 nodes, but 0, 1 and 2 form a cycle and node 3 has no edge at all.

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

    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 any other count, the answer is false. Fewer edges leave some node cut off, and more edges force a cycle.

    The count alone isn't enough, as the third example shows. With exactly n - 1 edges, though, the graph is a tree exactly when no edge closes a cycle. If every edge joins two separate groups of nodes, each edge merges two groups into one, and the n single nodes we started with end up as a single group: the graph is connected. A connected graph with no cycle is a tree.

    Union-find does the bookkeeping. It keeps each group as a tree of its own: every node points to a parent, and the root, the one node that is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root. For each edge:

    • find the roots of both ends;
    • if the roots are equal, the ends are already connected, so this edge would add a second path between them: a cycle;
    • otherwise merge the two groups.

    Two refinements keep the trees shallow. Union by size hangs the smaller tree under the larger one. Path halving makes each node passed during a search skip one level. Together they make each step cost O(α(n)) on average, where α is the inverse Ackermann function, below 5 for any n a computer can hold.

    A breadth-first or depth-first search from node 0 that checks that every node is reached also works once the count is right. This lesson uses union-find. The searching loop has no recursion, so a long chain of 100,000 nodes can't overflow the call stack.

    Here is the first example, edge by edge. The vectors are parent and size after each edge:

    edge [0, 1]: parent=[0, 0, 2, 3, 4] size=[2, 1, 1, 1, 1]
edge [0, 2]: parent=[0, 0, 0, 3, 4] size=[3, 1, 1, 1, 1]
edge [0, 3]: parent=[0, 0, 0, 0, 4] size=[4, 1, 1, 1, 1]
edge [1, 4]: parent=[0, 0, 0, 0, 0] size=[5, 1, 1, 1, 1]

    Every edge joined two different groups, and at the end all nodes lead to root 0, so the answer is true.

    Step by step

    1. Check the edge count. If edges.len() as i32 is not n - 1, return false. The cast turns the usize from len() into the type of n, so the two can be compared.
    2. Create parent as a Vec<usize> holding 0, 1, …, n - 1, by collecting the range 0..n as usize. Every node starts as the root of its own group. Nodes are usize so that they can index the vectors directly.
    3. Create size with vec![1; n as usize]. For a root r, size[r] counts the nodes in its group. Only the entries of roots are kept up to date.
    4. Loop over &edges, borrowing the vector.
    5. Find the root of edge[0] and store it in a mutable root_a, passing &mut parent because find changes the vector. The edge values are i32, so as usize turns them into indexes.
    6. Find the root of edge[1] in root_b.
    7. Return false when the roots are equal. This is the cycle test.
    8. Make root_a the larger group's root. If size[root_a] < size[root_b], swap the two variables with std::mem::swap. A node then moves one level deeper only when its group at least doubles, so no path to a root is longer than about log2(n) steps.
    9. Merge: set parent[root_b] to root_a.
    10. Update the size: size[root_a] += size[root_b]. The entry of root_b is never read again, because it is no longer a root.
    11. Return true after the loop. Every one of the n - 1 edges merged two groups, so the graph is connected and has no cycle.
    12. Write find as an associated function taking parent: &mut Vec<usize> and mut x: usize, returning the root.
    13. Loop while parent[x] != x, that is, while x is not a root.
    14. Path halving: set parent[x] to parent[parent[x]], so x points to its grandparent.
    15. Climb: set x to parent[x], which is now the old grandparent.
    16. Return x, the node that is its own parent.

    The solution in Rust

    impl Solution {
    fn valid_tree(n: i32, edges: Vec<Vec<i32>>) -> bool {
        if edges.len() as i32 != n - 1 {
            return false;
        }
        let mut parent: Vec<usize> = (0..n as usize).collect();
        let mut size = vec![1; n as usize];
        for edge in &edges {
            let mut root_a = Self::find(&mut parent, edge[0] as usize);
            let mut root_b = Self::find(&mut parent, edge[1] as usize);
            if root_a == root_b {
                return false;
            }
            if size[root_a] < size[root_b] {
                std::mem::swap(&mut root_a, &mut root_b);
            }
            parent[root_b] = root_a;
            size[root_a] += size[root_b];
        }
        true
    }

    fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
        while parent[x] != x {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        x
    }
}

    The Rust details worth a closer look:

    • Collecting a range. (0..n as usize) is a range of usize values, and collect() gathers them into the collection named by the type on parent. Without Vec<usize> on the left, the compiler wouldn't know what to build.
    • Type of size. vec![1; n as usize] names no element type. It is inferred from size[root_a] += size[root_b] and the comparison of two entries, and defaults to i32.
    • Borrowing. for edge in &edges borrows the vector, and edge is a &Vec<i32>. &mut parent lends parent mutably for the duration of the find call only, so the next line can use it again.
    • Why root_a and root_b are mut. They are reassigned only by the swap. std::mem::swap(&mut root_a, &mut root_b) takes two mutable borrows and exchanges the values behind them.
    • mut x. The parameter is a copy of the caller's number. mut lets the function move it up the tree without changing the caller's variable.
    • Loop instead of recursion. A recursive find could go as deep as the tree is tall. The loop uses no call stack, so the depth of the tree doesn't matter.
    • Final expressions. true and x have no semicolon, so they are the values the functions return.

    Complexity

    Time: O((n + e)·α(n)). The edge count is checked first, so at most n - 1 edges are processed, and building the vectors takes O(n). Each edge makes two find calls, which cost O(α(n)) on average thanks to union by size and path halving. That is nearly O(n + e).

    Space: O(n). The parent and size vectors hold one number per node.

    Edge cases and common mistakes

    • Counting edges and stopping. The third example has the right count and is still not a tree. The cycle check is required.
    • Skipping the count. Without it, n = 2 with no edges would reach true, since no edge closes a cycle, but the two nodes aren't connected. The function returns false because 0 is not n - 1 = 1.
    • A single node. For n = 1 and no edges, the count is 0, which equals n - 1, the loop doesn't run, and the answer is true.
    • Disconnected pieces. For n = 4 and edges = [[0, 1], [2, 3]] the count is 2, not 3, so the answer is false.
    • Edge order and direction. The edges are undirected, so [[3, 2], [2, 1], [1, 0]] with n = 4 is a tree too, and the order of the edges doesn't matter.
    • Comparing nodes instead of roots. The test is on roots. Two nodes can be connected without either being the root of anything.
    • Forgetting the size update. Union by size depends on size being right for the roots. Skipping the update makes the trees deeper but doesn't change any answer.
    • Mixed integer types. n and the edge values are i32, while indexes are usize. Each cast sits where a value is used as an index or compared with len().

    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 = 1, edges = [] gives true.
    • n = 2, edges = [] gives false.
    • n = 4, edges = [[0, 1], [2, 3]] gives false.
    • n = 4, edges = [[0, 1], [1, 2], [2, 3]] gives true.
    • n = 4, edges = [[3, 2], [2, 1], [1, 0]] gives true.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free