← 전체 회차
a-091-graph-valid-tree2026-08-19mediumleetcode #261neetcode150

그래프 유효 트리

#depth-first-search#breadth-first-search#union-find#graph
↗ leetcode #261 · a-091-graph-valid-tree
01

문제

· problem
P.a-091-graph-valid-tree

그래프 유효 트리

↗ leetcode #261

n개의 노드가 0부터 n-1까지 레이블이 지정된 그래프가 있습니다. edges 배열이 주어지고, edges[i] = [ai, bi]는 노드 ai와 bi 사이의 무방향 간선을 나타냅니다. 간선이 유효한 트리를 형성하면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 유효한 트리는 모든 두 꼭짓점이 정확히 하나의 경로로 연결된 무방향 그래프입니다. 즉, 순환이 없는 모든 연결된 그래프는 트리입니다.

제약
  • · 1 ≤ n ≤ 2000
  • · 0 ≤ edges.length ≤ 2000
  • · edges[i].length == 2
  • · 0 ≤ ai, bi < n
  • · ai != bi
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
5
[[0,1],[0,2],[0,3],[1,4]]
true
example 2input → output
5
[[0,1],[1,2],[2,3],[1,3],[1,4]]
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    유효한 트리의 필수 조건은 무엇인가요?
  • ☐
    순환이 없지만 연결되지 않은 그래프는 트리인가요?
  • ☐
    DFS에서 부모 노드를 건너뛰는 이유는?
  • ☐
    간선이 정확히 n-1개이면 항상 트리인가요?
  • ☐
    노드 0부터 DFS를 시작하는 이유는?
  • ☐
    자기 루프(self-loop)가 있으면 트리가 될 수 있나요?
  • ☐
    Union-Find 방식은 어떻게 순환을 감지하나요?
  • ☐
    n=0일 때는 어떻게 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 엣지 케이스 처리
○
○
if n == 0: return False
○
if len(edges) == 0: return True
step 2· 인접 리스트 초기화 및 그래프 구축
○
○
adj = [[] for _ in range(n)]; [adj[n1].append(n2) for n1, n2 in edges]
○
adj = {i: [] for i in range(n)}; adj[n1].extend([n2, n1]) for n1, n2 in edges
step 3· 방문 집합 초기화 및 DFS 함수 정의
○
○
visit = [False] * n; def dfs(i): ...
○
visit = set(); def dfs(i): ...
step 4· 순환 감지│ 중첩
○
○
if i in visit: return True
○
if i != 0 and i in visit: return False
step 5· 현재 노드 방문 표시│ 중첩
○
○
if i not in visit: visit.add(i)
step 6· 이웃 노드 탐색 (부모 건너뛰기)│ 중첩
○
○
for j in adj[i]: if i != j and not dfs(j, i): return False
○
for j in adj[i]: if not dfs(j, i): return False
step 7· 연결성 및 무순환성 최종 검증
○
○
return dfs(0, -1) and len(edges) == n - 1
○
return n == len(visit) and dfs(0, -1)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04
문제풀이 · 트레이스
· solve
solution.py
1
# Problem is free on Lintcode
2
class Solution:
3
    """
4
    @param n: An integer
5
    @param edges: a list of undirected edges
6
    @return: true if it's a valid tree, or false
7
    """
8
9
    def validTree(self, n, edges):
10
        if not n:
11
            return True
12
        adj = {i: [] for i in range(n)}
13
        for n1, n2 in edges:
14
            adj[n1].append(n2)
15
            adj[n2].append(n1)
16
17
        visit = set()
18
19
        def dfs(i, prev):
20
            if i in visit:
21
                return False
22
23
            visit.add(i)
24
            for j in adj[i]:
25
                if j == prev:
26
                    continue
27
                if not dfs(j, i):
28
                    return False
29
            return True
30
31
        return dfs(0, -1) and n == len(visit)
32
    
33
    
34
    
35
    # alternative solution via DSU O(ElogV) time complexity and 
36
    # save some space as we don't recreate graph\tree into adjacency list prior dfs and loop over the edge list directly
37
    class Solution:
38
    """
39
    @param n: An integer
40
    @param edges: a list of undirected edges
41
    @return: true if it's a valid tree, or false
42
    """
43
    def __find(self, n: int) -> int:
44
        while n != self.parents.get(n, n):
45
            n = self.parents.get(n, n)
46
        return n
47
48
    def __connect(self, n: int, m: int) -> None:
49
        pn = self.__find(n)
50
        pm = self.__find(m)
51
        if pn == pm:
52
            return
53
        if self.heights.get(pn, 1) > self.heights.get(pm, 1):
54
            self.parents[pn] = pm
55
        else:
56
            self.parents[pm] = pn
57
            self.heights[pm] = self.heights.get(pn, 1) + 1
58
        self.components -= 1
59
60
    def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
61
        # init here as not sure that ctor will be re-invoked in different tests
62
        self.parents = {}
63
        self.heights = {}
64
        self.components = n
65
66
        for e1, e2 in edges:
67
            if self.__find(e1) == self.__find(e2):  # 'redundant' edge
68
                return False
69
            self.__connect(e1, e2)
70
71
        return self.components == 1  # forest contains one tree
72
73
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
5
[[0,1],[0,2],[0,3],[1,4]]
→
true
case 2
5
[[0,1],[1,2],[2,3],[1,3],[1,4]]
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.