261. Graph Valid Tree

Problem Statement

link: LeetCode.cn LeetCode ou 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.

Example:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false

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.

Solution Approach

The solution checks if the graph is connected and acyclic by performing a depth-first search (DFS) from an initial node and verifying that all nodes are visited and the graph has exactly n - 1 edges.

Algorithm

1. Edge Count Check: Ensure the number of edges is exactly n - 1, which is a necessary condition for a valid tree.
2. DFS for Acyclic Property: Use depth-first search (DFS) to detect cycles and confirm that the graph is acyclic by checking if any node is revisited.
3. Connectedness Verification: Verify that all nodes are visited during the DFS, ensuring that the graph is fully connected.

Implement

    class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # if there is a loop it is not a tree
        if not n:
            return True
        adj = defaultdict(list)
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        visit = set()
        def dfs(i, prev):
            if i in visit:
                return False
            
            visit.add(i)
            for j in adj[i]:
                if j == prev:
                    continue
                if not dfs(j, i):
                    return False
            return True
            
        return dfs(0, -1)
     

    
    

Twitter  facebook  Email