Back to DSA

Graph Valid Tree

medium
Acceptance: 46%
GraphsUnion FindDFS

Given n nodes numbered 0 through n-1 and a list of undirected edges, determine whether the graph forms a valid tree. A valid tree is connected, has no cycles, and contains exactly n-1 edges.

Examples

Example 1:
Input:n = 4, edges = [[0,1],[0,2],[0,3]]
Output:true
Explanation: A star graph with 4 nodes and 3 edges; connected and acyclic.
Example 2:
Input:n = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output:false
Explanation: Four nodes with four edges form a cycle.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumShortest Path in Binary Matrixmedium
00:00
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int px = find(parent, e[0]), py = find(parent, e[1]);
            if (px == py) return false;
            parent[px] = py;
        }
        return true;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}
Time complexityO(E * alpha(V))
Space complexityO(V)