Graph is Valid Tree

XXX. Valid Tree

Union-Find

Graph Theory

Problem Statement:

Given n nodes labeled from 0 to n-1 and a list of edges, write a function to check if these edges form a valid tree.

A graph is a valid tree if it satisfies the following conditions:

• It is fully connected (all nodes are reachable).
• It contains no cycles.

Algorithm:

The problem is solved using the Union-Find (Disjoint Set Union) approach:

1. Initialize a parent array where each node is its own parent (represented by -1).
2. Iterate through each edge in the graph:
   • For each edge, find the roots of its two nodes using the find function.
   • If the roots of the two nodes are the same, a cycle exists, and the graph is not a tree.
   • Otherwise, union the two nodes to connect them.
3. After processing all edges, check if the number of edges is exactly n - 1 (a tree with n nodes has n - 1 edges).

Complexity:

Time Complexity: O(E + V), where E is the number of edges and V is the number of nodes. This accounts for processing edges and union-find operations.
Space Complexity: O(V), for the parent array.

Java Implementation:

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // Initialize the parent array
        int[] parent = new int[n];
        Arrays.fill(parent, -1); // Each node is its own parent initially

        // Process each edge
        for (int[] edge : edges) {
            int a = find(edge[0], parent); // Find root of the first node
            int b = find(edge[1], parent); // Find root of the second node

            if (a == b) return false; // Cycle detected

            union(a, b, parent); // Union the two nodes
        }

        // Check if the number of edges is exactly n - 1
        return n == edges.length + 1;
    }

    public int find(int i, int[] parent) {
        if (parent[i] < 0) return i; // Node is its own parent
        parent[i] = find(parent[i], parent); // Path compression for optimization
        return parent[i];
    }

    public void union(int a, int b, int[] parent) {
        if (parent[a] < parent[b]) { // Weighted union
            parent[a] += parent[b]; // Merge smaller tree into larger tree
            parent[b] = a;
        } else {
            parent[b] += parent[a];
            parent[a] = b;
        }
    }
}