Start learning free

LESSON 469 OF 535 · GRAPHS

Graph Valid Tree in C++: Union-Find in Near-Linear Time

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

You have a graph of n nodes, numbered from 0 to n - 1, and a vector 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 18
    Ctrl + Enter to check

    C++ · GRAPHS

    Graph Valid Tree in C++, explained

    Problem overview

    The function validTree receives n, the number of nodes (numbered 0 to n - 1), and a vector<vector<int>> called edges, where each edge is a pair of nodes. It returns true when these edges make the graph a tree. A tree is connected, so 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.

    With 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. With [0,1] [1,2] [2,3] [1,3] [1,4] it is false: 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 false too. The count of 3 edges is the number a tree of 4 nodes has, but 0, 1 and 2 form a cycle and node 3 has no edge at all.

    The lesson asks for time close to O(n + e), more exactly 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. With fewer, some node is cut off from the rest. With more, some edge closes a cycle. So the first check is on the count.

    With exactly n - 1 edges, the graph is a tree exactly when no edge closes a cycle. Add the edges one by one, keeping track of which nodes are already connected. If an edge joins two separate groups, it merges them. If both ends are already in the same group, they are connected through other edges, so this edge adds a second path between them: a cycle. When every one of the n - 1 edges has merged two groups, the n single nodes have become one group, so the graph is connected and has no cycle.

    Keeping track of groups is the job of union-find. Each group is stored as a tree of parent pointers, and its 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. Two refinements keep the trees shallow: union by size hangs the smaller tree under the larger one, and path halving shortens the path every time a node is looked up. Together they make each operation cost O(α(n)), 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 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 100,000 nodes can run out of call stack. Union-find has no recursion at all.

    Step by step

    1. Check the edge count. If edges.size() is not n - 1, return false.
    2. Create parent, a vector<int> of size n. parent[x] is the parent of node x.
    3. Create size, a vector<int> of size n filled with 1. size[r] counts the nodes of the group whose root is r. Only the roots' entries are kept up to date.
    4. Loop over the nodes and set parent[i] = i, so every node starts as the root of a group of one.
    5. Loop over the edges with auto& edge.
    6. Find both roots: rootA from edge[0] and rootB from edge[1], using a helper named find that the lesson writes at the end.
    7. Detect the cycle. If rootA == rootB, the two ends are already connected: return false.
    8. Union by size. If size[rootA] < size[rootB], swap the two roots, so rootA is the root of the larger group.
    9. Merge: set parent[rootB] = rootA.
    10. Update the size: size[rootA] += size[rootB]. rootB is not a root any more, so its size is never read again.
    11. Return true after the loop: no edge closed a cycle.
    12. Write find as a method taking vector<int>& parent and an int x, returning the root of x's group.
    13. Loop while parent[x] != x. A loop needs no call stack, however long the walk is.
    14. Halve the path. Set parent[x] = parent[parent[x]], so x skips one level.
    15. Move up with x = parent[x], which is now the old grandparent.
    16. Return x, the root.

    The solution in C++

    class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) {
            return false;
        }
        vector<int> parent(n);
        vector<int> size(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        for (auto& edge : edges) {
            int rootA = find(parent, edge[0]);
            int rootB = find(parent, edge[1]);
            if (rootA == rootB) {
                return false;
            }
            if (size[rootA] < size[rootB]) {
                swap(rootA, rootB);
            }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
        }
        return true;
    }

    int find(vector<int>& parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
};

    The C++ details worth a closer look:

    • Signed against unsigned. edges.size() is unsigned and n - 1 is an int, so the comparison converts the int to unsigned. That is harmless here because n is at least 1, so n - 1 is never negative. With n = 0 it would become a huge number.
    • vector<int> size(n, 1) and size(). A local variable named size is fine in this method, since edges.size() is a member call and is not affected by it.
    • References. find takes vector<int>& because it changes parent while halving paths. Without the & each call would work on a copy of the whole vector, which costs O(n) and loses the changes. auto& edge reads each edge in place instead of copying it.
    • The parameter x is a copy. Moving x up inside find changes only the method's own number.
    • swap(rootA, rootB) exchanges the values of two variables.

    Complexity

    Time: O((n + e)·α(n)), nearly O(n + e). Initialising the arrays is O(n). The loop makes two find calls and at most one merge per edge. Since e equals n - 1 after the count check, the whole function is close to linear.

    Space: O(n). The parent and size vectors have n entries each. find uses a loop, so there is no recursion stack.

    Edge cases and common mistakes

    • A single node. n = 1 with no edges gives true: the count 0 equals n - 1, and the loop doesn't run.
    • Two nodes with no edge. n = 2 with no edges gives false: the count 0 is not 1.
    • Two nodes with one edge. n = 2 and [0,1] gives true.
    • The right count is not enough. The example with 4 nodes and edges 0-1, 1-2 and 2-0 has 3 edges and still gives false. The cycle check is what rejects it, as the third edge finds both ends under the same root.
    • No cycle is not enough either. Fewer than n - 1 edges can never connect n nodes, and the count check rejects them before any merging.
    • Merging roots incorrectly. The edge must be handled through find, not through the nodes' own parent entries. A node's parent is not necessarily its root.
    • A recursive search on a long path. Nodes 0 to 99,999 in a line make a recursive DFS 100,000 calls deep. Union-find avoids that.

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