수업 목표 및 핵심 역량

- 방향 관계망 내 서로 완벽히 도달 가능한 사이클 서브그룹을 추려내는 역량을 체득합니다. - 지수 복잡도의 모든 정점 1회 순회 문제를 비트마스킹과 메모이제이션으로 개선합니다. - 네트워크 통로 용량 제한에서의 최대 흐름을 찾고 잔여 용량 역방향 에지를 제어합니다. - 이분 매칭의 효율적인 양보(Augmenting Path) 분배 구조를 파이썬으로 구현합니다.

Tarjan's SCC 탐색

- DFS의 조상 방문 정보와 스택을 활용한 $O(V+E)$ SCC 분류

# 8061번: 강한 연결 요소 발췌
if low[u] == visited[u]:
    scc = []
    while True:
        curr = stack.pop()
        in_stack[curr] = False
        scc.append(curr)
        if curr == u:
            break
    sccs.append(sorted(scc))

해밀턴 경로 비트마스크 DP

- $O(2^N \cdot N^2)$ 동적 계획법 상태 전이

# 8062번: 해밀턴 경로 발췌
# N번 방(도착 도시) 도달 시 중간 전이 차단
if u == n:
    continue
for v in adj[u]:
    if not (mask & (1 << (v - 1))):
        next_mask = mask | (1 << (v - 1))
        dp[next_mask][v] = (dp[next_mask][v] + dp[mask][u]) % MOD

Edmonds-Karp 최대 유량

- BFS 기반 최단 증가 경로 추적 및 역방향 잔여 용량 수정

# 8063번: 최대 유량 발췌
while v != 1:
    u = parent[v]
    capacity[(u, v)] -= curr_flow
    capacity[(v, u)] += curr_flow
    v = u

이분 매칭 (DFS)

- DFS 양보 재귀 호출을 통한 최대 매칭 수 확보

# 8064번: 이분 매칭 발췌
def dfs(u):
    for v in adj[u]:
        if visited[v]:
            continue
        visited[v] = True
        if match[v] < 0 or dfs(match[v]):
            match[v] = u
            return True
    return False

오류 예방 및 안정성 체크

- **파이썬 DFS 재귀 상한 조정**: sys.setrecursionlimit 필수 적용으로 런타임 Stack Overflow 차단 - **해밀턴 경로 끝 노드 예외**: 1번 출발, N번 목적지 고정이므로 1번을 맨 처음에만 켜고, N번 도달 시 그 이상의 전이를 방지하여 정확성 확보 - **역류(Residual Flow)의 정확성**: 최대 유량 탐색에서 역방향 간선에 유량을 더해주는 logic을 빼먹지 않도록 대칭적 갱신 확인