17_scc.py - Examples

  1"""
  2강한 연결 요소 (SCC - Strongly Connected Components)
  3Strongly Connected Components
  4
  5방향 그래프에서 서로 도달 가능한 정점들의 최대 집합을 찾습니다.
  6"""
  7
  8from typing import List, Tuple, Set
  9from collections import defaultdict
 10
 11
 12# =============================================================================
 13# 1. Kosaraju 알고리즘
 14# =============================================================================
 15
 16def kosaraju_scc(n: int, edges: List[Tuple[int, int]]) -> List[List[int]]:
 17    """
 18    Kosaraju 알고리즘으로 SCC 찾기
 19    시간복잡도: O(V + E)
 20    공간복잡도: O(V + E)
 21
 22    1. 정방향 DFS로 종료 순서 스택 구성
 23    2. 역방향 그래프에서 스택 순서대로 DFS
 24    """
 25    # 정방향/역방향 그래프
 26    graph = defaultdict(list)
 27    reverse_graph = defaultdict(list)
 28
 29    for u, v in edges:
 30        graph[u].append(v)
 31        reverse_graph[v].append(u)
 32
 33    # 1단계: 정방향 DFS로 종료 순서 기록
 34    visited = [False] * n
 35    finish_stack = []
 36
 37    def dfs1(node: int):
 38        visited[node] = True
 39        for neighbor in graph[node]:
 40            if not visited[neighbor]:
 41                dfs1(neighbor)
 42        finish_stack.append(node)
 43
 44    for i in range(n):
 45        if not visited[i]:
 46            dfs1(i)
 47
 48    # 2단계: 역방향 DFS로 SCC 찾기
 49    visited = [False] * n
 50    sccs = []
 51
 52    def dfs2(node: int, component: List[int]):
 53        visited[node] = True
 54        component.append(node)
 55        for neighbor in reverse_graph[node]:
 56            if not visited[neighbor]:
 57                dfs2(neighbor, component)
 58
 59    while finish_stack:
 60        node = finish_stack.pop()
 61        if not visited[node]:
 62            component = []
 63            dfs2(node, component)
 64            sccs.append(component)
 65
 66    return sccs
 67
 68
 69# =============================================================================
 70# 2. Tarjan 알고리즘
 71# =============================================================================
 72
 73def tarjan_scc(n: int, edges: List[Tuple[int, int]]) -> List[List[int]]:
 74    """
 75    Tarjan 알고리즘으로 SCC 찾기
 76    시간복잡도: O(V + E)
 77    공간복잡도: O(V)
 78
 79    low[v] = v에서 도달 가능한 최소 발견 시간
 80    """
 81    graph = defaultdict(list)
 82    for u, v in edges:
 83        graph[u].append(v)
 84
 85    disc = [-1] * n  # 발견 시간
 86    low = [-1] * n   # low-link 값
 87    on_stack = [False] * n
 88    stack = []
 89    sccs = []
 90    time = [0]  # 전역 시간
 91
 92    def dfs(node: int):
 93        disc[node] = low[node] = time[0]
 94        time[0] += 1
 95        stack.append(node)
 96        on_stack[node] = True
 97
 98        for neighbor in graph[node]:
 99            if disc[neighbor] == -1:  # 미방문
100                dfs(neighbor)
101                low[node] = min(low[node], low[neighbor])
102            elif on_stack[neighbor]:  # 스택에 있음 (back edge)
103                low[node] = min(low[node], disc[neighbor])
104
105        # SCC 루트 발견
106        if low[node] == disc[node]:
107            component = []
108            while True:
109                v = stack.pop()
110                on_stack[v] = False
111                component.append(v)
112                if v == node:
113                    break
114            sccs.append(component)
115
116    for i in range(n):
117        if disc[i] == -1:
118            dfs(i)
119
120    return sccs
121
122
123# =============================================================================
124# 3. SCC 축약 그래프 (DAG)
125# =============================================================================
126
127def build_scc_dag(n: int, edges: List[Tuple[int, int]]) -> Tuple[List[List[int]], List[List[int]], List[int]]:
128    """
129    SCC를 찾고 축약 그래프(DAG) 구성
130    반환: (sccs, scc_graph, node_to_scc)
131    """
132    sccs = tarjan_scc(n, edges)
133
134    # 각 노드가 속한 SCC 매핑
135    node_to_scc = [-1] * n
136    for i, component in enumerate(sccs):
137        for node in component:
138            node_to_scc[node] = i
139
140    # SCC 간의 간선 (DAG)
141    scc_edges = set()
142    for u, v in edges:
143        scc_u = node_to_scc[u]
144        scc_v = node_to_scc[v]
145        if scc_u != scc_v:
146            scc_edges.add((scc_u, scc_v))
147
148    scc_graph = defaultdict(list)
149    for u, v in scc_edges:
150        scc_graph[u].append(v)
151
152    return sccs, dict(scc_graph), node_to_scc
153
154
155# =============================================================================
156# 4. 2-SAT 문제
157# =============================================================================
158
159class TwoSAT:
160    """
161    2-SAT 문제 해결기
162    n개의 불린 변수와 2-CNF 조건식
163
164    변수 x_i: 노드 2*i (true), 노드 2*i+1 (false)
165    조건 (a ∨ b): ¬a → b, ¬b → a
166    """
167
168    def __init__(self, n: int):
169        self.n = n
170        self.graph = defaultdict(list)
171        self.reverse_graph = defaultdict(list)
172
173    def _var(self, x: int, negated: bool) -> int:
174        """변수를 그래프 노드로 변환"""
175        return 2 * x + (1 if negated else 0)
176
177    def _neg(self, node: int) -> int:
178        """노드의 부정"""
179        return node ^ 1
180
181    def add_clause(self, x: int, neg_x: bool, y: int, neg_y: bool):
182        """
183        조건 추가: (x ∨ y)
184        neg_x: x가 부정인지
185        neg_y: y가 부정인지
186        """
187        # (x ∨ y) ≡ (¬x → y) ∧ (¬y → x)
188        node_x = self._var(x, neg_x)
189        node_y = self._var(y, neg_y)
190
191        # ¬x → y
192        self.graph[self._neg(node_x)].append(node_y)
193        self.reverse_graph[node_y].append(self._neg(node_x))
194
195        # ¬y → x
196        self.graph[self._neg(node_y)].append(node_x)
197        self.reverse_graph[node_x].append(self._neg(node_y))
198
199    def solve(self) -> Tuple[bool, List[bool]]:
200        """
201        2-SAT 해결
202        반환: (만족 가능 여부, 각 변수의 값)
203        """
204        total_nodes = 2 * self.n
205
206        # Kosaraju로 SCC 찾기
207        visited = [False] * total_nodes
208        finish_stack = []
209
210        def dfs1(node: int):
211            visited[node] = True
212            for neighbor in self.graph[node]:
213                if not visited[neighbor]:
214                    dfs1(neighbor)
215            finish_stack.append(node)
216
217        for i in range(total_nodes):
218            if not visited[i]:
219                dfs1(i)
220
221        visited = [False] * total_nodes
222        scc_id = [-1] * total_nodes
223        current_scc = 0
224
225        def dfs2(node: int):
226            visited[node] = True
227            scc_id[node] = current_scc
228            for neighbor in self.reverse_graph[node]:
229                if not visited[neighbor]:
230                    dfs2(neighbor)
231
232        while finish_stack:
233            node = finish_stack.pop()
234            if not visited[node]:
235                dfs2(node)
236                current_scc += 1
237
238        # 만족 가능성 검사
239        for i in range(self.n):
240            if scc_id[2 * i] == scc_id[2 * i + 1]:
241                return False, []
242
243        # 해 구성 (나중에 발견된 SCC = 더 작은 SCC ID = 더 높은 위상 순서)
244        assignment = [False] * self.n
245        for i in range(self.n):
246            # scc_id가 작으면 위상 순서에서 뒤에 있음 → 그 값이 true
247            assignment[i] = scc_id[2 * i] > scc_id[2 * i + 1]
248
249        return True, assignment
250
251
252# =============================================================================
253# 5. 실전 문제: 학교 도달 가능성
254# =============================================================================
255
256def min_roads_to_connect(n: int, roads: List[Tuple[int, int]]) -> int:
257    """
258    모든 학교가 서로 도달 가능하게 하려면 추가해야 할 최소 도로 수
259    = max(진입 차수 0인 SCC 수, 진출 차수 0인 SCC 수)
260    (SCC가 1개면 0)
261    """
262    if not roads:
263        return n - 1 if n > 1 else 0
264
265    sccs, scc_graph, node_to_scc = build_scc_dag(n, roads)
266
267    if len(sccs) == 1:
268        return 0
269
270    # 각 SCC의 진입/진출 차수
271    in_degree = [0] * len(sccs)
272    out_degree = [0] * len(sccs)
273
274    for scc_u, neighbors in scc_graph.items():
275        out_degree[scc_u] = len(neighbors)
276        for scc_v in neighbors:
277            in_degree[scc_v] += 1
278
279    # 진입/진출 차수 0인 SCC 개수
280    sources = sum(1 for d in in_degree if d == 0)
281    sinks = sum(1 for d in out_degree if d == 0)
282
283    return max(sources, sinks)
284
285
286# =============================================================================
287# 6. 실전 문제: 중요 노드 (Articulation Points 유사)
288# =============================================================================
289
290def find_critical_nodes(n: int, edges: List[Tuple[int, int]]) -> List[int]:
291    """
292    제거하면 SCC 개수가 증가하는 노드들 찾기
293    (간단한 brute force 구현)
294    """
295    original_scc_count = len(tarjan_scc(n, edges))
296    critical = []
297
298    for remove_node in range(n):
299        # 해당 노드 제외한 그래프
300        new_edges = [(u, v) for u, v in edges if u != remove_node and v != remove_node]
301
302        # 노드 재매핑
303        remaining = [i for i in range(n) if i != remove_node]
304        if not remaining:
305            continue
306
307        node_map = {old: new for new, old in enumerate(remaining)}
308        remapped_edges = [(node_map[u], node_map[v]) for u, v in new_edges
309                          if u in node_map and v in node_map]
310
311        new_scc_count = len(tarjan_scc(len(remaining), remapped_edges))
312
313        if new_scc_count > original_scc_count - 1:  # -1은 제거된 노드의 SCC
314            critical.append(remove_node)
315
316    return critical
317
318
319# =============================================================================
320# 테스트
321# =============================================================================
322
323def main():
324    print("=" * 60)
325    print("강한 연결 요소 (SCC) 예제")
326    print("=" * 60)
327
328    # 그래프 구성
329    #   0 → 1 → 2
330    #   ↑   ↓   ↓
331    #   4 ← 3 → 5 → 6
332    #       ↑       ↓
333    #       └───────┘
334
335    n = 7
336    edges = [
337        (0, 1), (1, 2), (1, 3), (2, 5),
338        (3, 4), (4, 0), (3, 5), (5, 6), (6, 3)
339    ]
340
341    # 1. Kosaraju 알고리즘
342    print("\n[1] Kosaraju 알고리즘")
343    sccs = kosaraju_scc(n, edges)
344    print(f"    간선: {edges}")
345    print(f"    SCC: {sccs}")
346
347    # 2. Tarjan 알고리즘
348    print("\n[2] Tarjan 알고리즘")
349    sccs = tarjan_scc(n, edges)
350    print(f"    SCC: {sccs}")
351
352    # 3. SCC 축약 DAG
353    print("\n[3] SCC 축약 그래프 (DAG)")
354    sccs, scc_graph, node_to_scc = build_scc_dag(n, edges)
355    print(f"    SCC: {sccs}")
356    print(f"    노드→SCC: {node_to_scc}")
357    print(f"    SCC 간선: {dict(scc_graph)}")
358
359    # 4. 2-SAT 문제
360    print("\n[4] 2-SAT 문제")
361    # (x0 ∨ x1) ∧ (¬x0 ∨ x2) ∧ (¬x1 ∨ ¬x2)
362    sat = TwoSAT(3)
363    sat.add_clause(0, False, 1, False)  # x0 ∨ x1
364    sat.add_clause(0, True, 2, False)   # ¬x0 ∨ x2
365    sat.add_clause(1, True, 2, True)    # ¬x1 ∨ ¬x2
366
367    solvable, assignment = sat.solve()
368    print(f"    조건: (x0 ∨ x1) ∧ (¬x0 ∨ x2) ∧ (¬x1 ∨ ¬x2)")
369    print(f"    해결 가능: {solvable}")
370    if solvable:
371        print(f"    해: x0={assignment[0]}, x1={assignment[1]}, x2={assignment[2]}")
372
373    # 불가능한 2-SAT
374    print("\n    불가능한 경우:")
375    sat2 = TwoSAT(1)
376    sat2.add_clause(0, False, 0, False)  # x0 ∨ x0 = x0
377    sat2.add_clause(0, True, 0, True)    # ¬x0 ∨ ¬x0 = ¬x0
378    solvable2, _ = sat2.solve()
379    print(f"    조건: x0 ∧ ¬x0")
380    print(f"    해결 가능: {solvable2}")
381
382    # 5. 학교 연결
383    print("\n[5] 학교 연결 문제")
384    school_roads = [(0, 1), (1, 2), (2, 0), (3, 4), (4, 3)]
385    min_roads = min_roads_to_connect(5, school_roads)
386    print(f"    도로: {school_roads}")
387    print(f"    추가 필요 도로: {min_roads}개")
388
389    # 6. 알고리즘 비교
390    print("\n[6] Kosaraju vs Tarjan 비교")
391    print("    | 특성           | Kosaraju      | Tarjan        |")
392    print("    |----------------|---------------|---------------|")
393    print("    | 시간복잡도     | O(V + E)      | O(V + E)      |")
394    print("    | DFS 횟수       | 2번           | 1번           |")
395    print("    | 역그래프 필요  | 예            | 아니오        |")
396    print("    | 구현 난이도    | 쉬움          | 보통          |")
397
398    print("\n" + "=" * 60)
399
400
401if __name__ == "__main__":
402    main()