Check two conditions: the edge count must be exactly n-1, and all nodes must be reachable from any starting node.

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

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Graph Valid Tree

Examples

Hints

Related Problems