LC 0261 [M] Graph Valid Tree - ALawliet/algorithms GitHub Wiki

prereq: https://github.com/codewithsenpai/algos/wiki/LC-0323-%5BM%5D-Number-of-Connected-Components-in-an-Undirected-Graph

in order to be a valid tree:

  1. it must not have loops
  2. all nodes must be connected (must be exactly 1 connected component)

it's valid if we don't detect a cycle, so BFS => no cross edge or DFS => no back edge

after reviewing this multiple times, the DFS seems simpler than BFS

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        G = {i: set() for i in range(n)}
        for u, v in edges:
            G[u].add(v) ; G[v].add(u)
            
        visited = set()
        parent = dict()
        
        def dfs(u): # has cycle
            visited.add(u)

            for v in G[u]:
                if v not in visited:
                    parent[v] = u
                    if dfs(v):
                        return True
                else:
                    if v != parent[u]:
                        return True
                    
            return False
        
        num_components = 0
        for i in range(n):
            if i not in visited:
                num_components += 1
                if num_components > 1:
                    return False
                if dfs(i):
                    return False
        return True
class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        G = {i: set() for i in range(n)} # i is a vertex and we store its set of neighbors as adj list
        for u, v in edges:
            G[u].add(v) ; G[v].add(u) # undirected: if u is connected to v, then v is also connected to u (u<->v)
        
        visited = set()
        parent = dict()

        def bfs_detected_cycle_cross_edge(i):
            Q = deque([i])
            visited.add(i)
            
            while Q:
                node = Q.popleft()
                
                for neighbor in G[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        parent[neighbor] = node
                        Q.append(neighbor)
                    else: # neighbor in visited
                        if neighbor != parent[node]: return True # is a cross edge
                        
            return False
        
        num_components = 0
        for i in range(n):
            if i not in visited:
                num_components += 1
                if num_components > 1: return False
                if bfs_detected_cycle_cross_edge(i): return False
        return True

"detect a cycle in a graph"

similar to [323. Number of Connected Components in an Undirected Graph] with # edge additions for cycle detection

a valid tree is a connected graph without any cycles

in an undirected graph:

  • BFS: has tree edges & cross edges (branch-to-branch), where cross edges indicate a cycle

  • DFS: has tree edges & back edges (upwards from child to ancestor), where back edges indicate a cycle

  • DFS back edge is a cycle because by definition it means there is a path all the way down from the ancestors to the descendants, then back up to an ancestor

  • DFS does not have cross edges because there cannot be an edge from a node in one branch to another branch (cause it goes down instead of across)

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # the edges are not the neighbors but the connections
        # so have to use this info to build the adj map of neighbors
        # python set() is implemented as hashtable with O(1) lookups
        G = {v: set() for v in range(n)}
        for v1, v2 in edges:
            # undirected: if v1 is connected to v2, then v2 is also connected to v1
            G[v1].add(v2) ; G[v2].add(v1)
        print(G)
        
        def bfs(v):
            Q = deque([v])
            visited.add(v)

            while Q:
                node = Q.popleft()

                for neighbor in G[node]:
                    if neighbor not in visited:
                        # TREE EDGE
                        visited.add(neighbor)
                        parent[neighbor] = node 
                        Q.append(neighbor)
                    else:
                        if neighbor != parent[node]:
                            # CROSS EDGE = cycle detected
                            return True

            return False
        
        def dfs(node):
            visited.add(node)

            for neighbor in G[node]:
                if neighbor not in visited:
                    # TREE EDGE
                    parent[neighbor] = node
                    if dfs(neighbor) == True: return True
                        # current parent or some ancestor further up could be a BACK EDGE
                        # => there was a cycle detected in a previous subtree
                else:
                    if neighbor != parent[node]:
                        # BACK EDGE = cycle detected
                        return True

            return False
                        
        visited = set()
        parent = dict() # must track the parent to detect cycles: BFS (cross edges), DFS (back edges)

        num_components = 0
        has_cycle = False
        
        for v in range(n):
            if v not in visited:
                num_components += 1

                if num_components > 1: # 
                    has_cycle = True
                    break

                has_cycle = bfs(v)
                # has_cycle = dfs(v)

        return not has_cycle