Graphs(Valid Tree: 싸이클 탐지, 연결성): 261. Graph Valid Tree ☆★★★★

261. Graph Valid Tree

 

https://youtu.be/bXsUuownnoQ?si=hDkFB87rMA-fL6M4

 

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # 만약 노드의 개수가 0이라면, 빈 트리로 간주되므로 True 반환
        # If there are no nodes (n == 0), it's considered a valid empty tree.
        if not n:
            return True

        """
        유효한 트리가 되기 위한 조건 (Valid Tree Conditions):
        1. 노드 개수 - 1 == 간선 개수 (node count - 1 == edge count)
           - 트리에서는 노드의 개수가 n개라면, 간선의 개수는 반드시 n-1이어야 함.
        2. 모든 노드가 연결되어 있어야 함 (All nodes must be connected).
           - 시작 노드에서 탐색하여 모든 노드가 방문되었는지 확인.
        3. 싸이클이 없어야 함 (The graph must be acyclic).
           - 이미 방문한 노드를 부모 노드를 거치지 않고 다시 방문하면 싸이클이 존재.
        """

        # 1. valid tree 조건(1): 간선 개수 확인
        # 1. Check condition: node count - 1 == edge count
        if n - 1 != len(edges):
            print("node 개수 - 1 != 간선개수")  # 디버깅용 출력
            return False

        # 2. 인접 리스트를 생성하여 그래프를 표현
        # 2. Build the adjacency list to represent the graph.
        adj = {i: [] for i in range(n)}
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        # 3. 방문한 노드를 추적하기 위한 집합
        # 3. A set to track visited nodes.
        visit = set()

        # DFS 함수 정의
        # Define the DFS function.
        def dfs(i, prev):
            # 현재 노드를 이미 방문한 경우 싸이클 발생
            # If the current node is already visited, a cycle is detected.
            if i in visit:
                return False

            # 현재 노드를 방문으로 표시
            # Mark the current node as visited.
            visit.add(i)

            # 인접 노드들을 탐색
            # Explore all adjacent nodes.
            for j in adj[i]:
                # 이전 노드(부모 노드)는 건너뜀
                # Skip the previous (parent) node.
                if j == prev:
                    continue
                # 재귀적으로 DFS 호출, False 반환 시 즉시 종료
                # Recursively call DFS. If it returns False, exit immediately.
                if not dfs(j, i):
                    return False

            # 모든 인접 노드를 탐색한 경우 True 반환
            # Return True if all adjacent nodes are explored successfully.
            return True

        # 4. DFS 시작: 노드 0에서 시작하며 부모 노드를 -1로 설정 (-1은 유효하지 않은 노드 번호)
        # 4. Start DFS: Begin at node 0 with -1 as the parent node (invalid node number).
        # 조건: DFS가 True를 반환하고, 방문한 노드의 개수가 총 노드의 개수와 같아야 함.
        # Condition: DFS must return True and the number of visited nodes must equal the total nodes.
        return dfs(0, -1) and n == len(visit)

 

visited, visiting, parent 사용하는 코드

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # 그래프가 트리가 되려면, 
        # 1) 간선수 = 노드수 -1
        # 2) 모든 노드가 연결
        # 3) 싸이클 없어야 
        if not n:
            return True

        if (n-1) != len(edges):
            return False

        adj = {}
        for i in range(n):
            adj[i] = []
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        visited = set()
        visiting = set()

        def isNotCycle(node, parent):
            # Cycle 없으면 True, 싸이클 있으면 False
            if node in visited:
                return True
            if node in visiting:
                return False
            
            # 방문중 추가
            visiting.add(node)

            for nei in adj[node]:
                if nei == parent: # 부모 인지 확인
                    continue

                if isNotCycle(nei, node) == False: # 싸이클 있으면 False
                    return False
            visiting.remove(node) # 방문중 제거
            visited.add(node) # 방문 완료 추가
            return True # 정상 방문 완료
        
        for i in range(n):
            if i not in visited:
                if isNotCycle(i, -1) == False:
                    return False
        print(visited)
        return True if len(visited) == n else False