Start learning free

LESSON 473 OF 539 · GRAPHS

Graph Valid Tree in C#: Union-Find Cycle Check

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

    C# · GRAPHS

    Graph Valid Tree in C#, explained

    Problem overview

    ValidTree receives n, the number of nodes (numbered 0 to n - 1), and edges, an int[][] in which each edges[i] holds two nodes joined by an undirected edge. It returns true when the graph is a tree: connected, with 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. With 1-2, 2-3, 1-3 among the edges there is a cycle, so it is false. The third example, n = 4 with edges 0-1, 1-2, 2-0, has three edges, which is the right count for four nodes, but they form a triangle and node 3 is cut off. Counting edges is necessary, not sufficient.

    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. With more, some edge closes a cycle. So the first check is edges.Length != n - 1.

    When the count is right, the graph is a tree exactly when no edge closes a cycle. If every one of the n - 1 edges joins two separate groups, the n single nodes end up as one group, so the graph is connected and has no cycle.

    Union-find detects this. It keeps each group of connected nodes as a small tree of parent links. The root, the one node that is its own parent, names the group. For each edge, find the roots of both ends. Equal roots mean the ends are already connected, so this edge closes a cycle. Different roots mean the edge merges two groups.

    Two refinements keep the trees shallow: union by size puts the smaller tree under the larger one, and path halving makes each node passed during a search point to its grandparent. Together they make each operation almost constant time.

    Step by step

    1. Check the count. If edges.Length != n - 1, return false.
    2. Create parent and size as int arrays of length n. parent[x] is the parent of x, and size[r] counts the nodes in the group whose root is r.
    3. Initialise every node. A loop sets parent[i] = i (each node is the root of its own group) and size[i] = 1. New arrays hold zeros, so this loop is required.
    4. Visit each edge with foreach (int[] edge in edges).
    5. Find both roots with Find(parent, edge[0]) and Find(parent, edge[1]), into rootA and rootB.
    6. Detect the cycle. If rootA == rootB, return false.
    7. Union by size. If size[rootA] < size[rootB], swap the two variables with a tuple assignment, so that rootA is the root of the larger group.
    8. Merge. Set parent[rootB] = rootA and add size[rootB] to size[rootA].
    9. Return true after the loop: no edge closed a cycle.
    10. Write Find. While parent[x] != x, set parent[x] = parent[parent[x]] and then x = parent[x]. When the loop stops, x is the root, and the method returns it.

    The solution in C#

    class Solution {
    public bool ValidTree(int n, int[][] edges) {
        if (edges.Length != n - 1) {
            return false;
        }
        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        foreach (int[] edge in edges) {
            int rootA = Find(parent, edge[0]);
            int rootB = 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;
    }

    public int Find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

    The C# details worth knowing:

    • (rootA, rootB) = (rootB, rootA); builds a tuple from the right side and unpacks it into the variables on the left, which swaps them in one line without a temporary variable.
    • Arrays are reference types. Find receives the same parent array, so the path halving it does stays visible to ValidTree. Its parameter x is an int copy, so changing x inside Find does not touch the caller's variable.
    • Find uses a loop, not recursion, so a long chain of parents cannot overflow the call stack.
    • int[][] is a jagged array: an array of arrays. edges.Length is the number of edges, and each edge[0], edge[1] is a node.

    Complexity

    Time: O((n + e) * α(n)), nearly O(n + e), where e is the number of edges and α is the inverse Ackermann function, below 5 for any size a computer can hold. Since the count check forces e = n - 1, this is nearly linear in n.

    Space: O(n) for the two arrays.

    A breadth-first or depth-first search from node 0 that checks every node was reached also works once the count is right. For graphs this large, use a queue or an explicit stack: a recursive search down a path of 100,000 nodes can run out of call stack.

    Edge cases and common mistakes

    • One node, no edges. n = 1 with no edges returns true: zero edges is n - 1, and there is nothing to connect.
    • Several nodes, no edges. n = 2 with no edges returns false, by the count check.
    • Right count, wrong shape. n = 4 with 0-1, 1-2, 2-0 returns false: the third edge joins nodes that are already connected.
    • Checking cycles only. Without the count check, a graph with too few edges (a forest) would pass.
    • Forgetting to initialise parent. All zeros would make every node a child of node 0.
    • Comparing nodes instead of roots. Two nodes are connected when their roots are equal, not when the nodes are.

    Testing

    • n = 5, {{0,1},{0,2},{0,3},{1,4}} gives True.
    • n = 5, {{0,1},{1,2},{2,3},{1,3},{1,4}} gives False.
    • n = 4, {{0,1},{1,2},{2,0}} gives False.
    • n = 1, no edges, gives True.
    • n = 2, no edges, gives False.
    • n = 4, {{0,1},{2,3},{3,2}} gives False.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free