Skip to content
AI360Xpert
Back to Graphs
Medium

Graph Valid Tree

You have a graph of `n` nodes labeled from `0` to `n - 1`. You are given an integer `n` and a list of `edges` where `edges[i] = [ai, bi]` indicates that there is an undirected edge between nodes `ai` and `bi` in the graph. Return `true` if the edges of the given graph make up a valid tree, and `false` otherwise.

Examples

Input:n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output:true
The edges form a valid tree without any cycles.
Input:n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output:false
The edges [1,2], [2,3], [1,3] form a cycle, so the graph is not a valid tree.

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no self-loops or repeated edges.

Union Find

Approach

1. Intuition: For a graph to be a valid tree, it must satisfy two conditions: it must have exactly `n - 1` edges, and it must have no cycles. 2. We can first check if `edges.length == n - 1`. If not, we can immediately return `false` because the graph is either disconnected (fewer edges) or contains a cycle (more edges). 3. If it has exactly `n - 1` edges, we just need to verify that it is fully connected (or equivalently, has no cycles). We can use Union-Find for this. 4. We iterate through the edges. For each edge `(u, v)`, we try to union `u` and `v`. 5. If they are already in the same set (i.e., they have the same root), adding this edge would create a cycle. So we return `false`. 6. If we process all edges without finding any cycles, and we started with `n - 1` edges, then the graph is a valid tree. We return `true`.

Complexity Analysis

Time Complexity
O(V + E * α(V))
Space Complexity
O(V)

Time complexity is nearly O(V + E) as the union find operations take almost constant time. Since E = V - 1, it is essentially O(V). Space complexity is O(V) for the parent and rank arrays.

Solution.java
class Solution {    public boolean validTree(int n, int[][] edges) {        if (edges.length != n - 1) return false;                int[] parent = new int[n];        int[] rank = new int[n];                for (int i = 0; i < n; i++) {            parent[i] = i;            rank[i] = 1;        }                for (int[] edge : edges) {            if (!union(parent, rank, edge[0], edge[1])) {                return false; // Cycle detected            }        }                return true;    }        private int find(int[] parent, int n) {        if (parent[n] != n) {            parent[n] = find(parent, parent[n]);        }        return parent[n];    }        private boolean union(int[] parent, int[] rank, int n1, int n2) {        int p1 = find(parent, n1);        int p2 = find(parent, n2);                if (p1 == p2) {            return false;        }                if (rank[p1] > rank[p2]) {            parent[p2] = p1;            rank[p1] += rank[p2];        } else {            parent[p1] = p2;            rank[p2] += rank[p1];        }                return true;    }}