_261. Graph Valid Tree.md

261. Graph Valid Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : January 29, 2025

Last updated : January 29, 2025

---

Related Topics : Depth-First Search, Breadth-First Search, Union Find, Graph

Acceptance Rate : 49.1 %

---

Notes

• For a tree to be valid, $|E|=|V|-1$ must be true where $E$ is the edge set and $V$ is the vertex set
• Check for cycle starting from a random node -- track visited nodes
  • If any cycle is found, we return False
  • If no cycle is found, we continue
• Check if all nodes were visited
  • If all nodes visited, we return True
  • Else, we return False

In theory the all nodes visited check is all that we need as long as avoid infinite looping in cycles. However, it's more efficient if we break out early if a cycle is found.

The reason for the all nodes visited check after cycles is for graphs such as this:

     1          2
     |         / \
     3        4---5

This graph has 5 vertices and 4 edges which fulfills the first condition. It's possible we'll start our cycle check on vertex 1 wherein we won't have a cycle, but there's a cycle elsewhere.

---

Solutions

• m261.py

Python

m261.py

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1 :
            return False

        # Create edge map
        e = defaultdict(set)
        for u, v in edges :
            e[u].add(v)
            e[v].add(u)

        # Detect cycle to save runtime -- breaks out early if cycle detected otherwise attempts
        # to validate by visiting all n edges
        def dfs_detect_cycle(curr: int, prev: int, e: defaultdict, visited: Set[int]) -> bool :
            if curr in visited :
                return True
            visited.add(curr)
            if any(dfs_detect_cycle(nxt, curr, e, visited) for nxt in e[curr] if nxt != prev) :
                return (True, visited)
            return False

        # Since dfs_detect_cycle() is called first before the or, visited() will be
        # filled prior to len() being tested
        visited = set()
        if dfs_detect_cycle(1, None, e, visited) or not len(visited) == n :
            return False

        return True