[BOJ 2316] 도시 왕복하기 2

문제

---

https://www.acmicpc.net/problem/2316

풀이

---

도시 왕복하기 1에서 조건이 추가됐다.

일단 양방향 엣지로 바뀌었고, 각 노드도 최대 1번만 지날 수 있다.

각 노드 u, v에 대해, 새로운 노드 u’, v’을 만들어주고, 단방향 엣지 (u, u’), (v, v’)를 추가한다.

그리고 (u, v) 엣지가 존재하면, 두 단방향 엣지 (u’, v), (v’, u)로 나눠준다.

이렇게 되면 엣지 (u, u’) 때문에 노드 u를 최대 한 번만 지날 수 있다는 제약이 걸린다.

코드

---

import sys


def dfs(cur):
    if cur == 2:
        return 1
    
    for nxt in range(2, 2 * n + 1):
        if graph[cur][nxt] and not visit[nxt]:            
            visit[nxt] = 1
            if dfs(nxt):
                graph[cur][nxt] = 0
                graph[nxt][cur] = 1
                return 1
    
    return 0


n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (2 * n + 1) for _ in range(2 * n + 1)]

for i in range(1, n + 1):
    graph[i][i + n] = 1

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start + n][end] = 1
    graph[end + n][start] = 1

ans = 0
flow = 1
while flow:
    visit = [0] * (2 * n + 1)
    flow = dfs(1 + n)
    ans += flow

print(ans)