[BOJ 17412] 도시 왕복하기 1

문제

---

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

풀이

---

각 엣지를 최대 한 번씩만 지날 수 있다는 뜻은 capacity가 1이라는 것으로 해석할 수 있다.

1번 노드를 source, 2번 노드를 sink로 하는 flow network의 최대 유량을 구해주면 된다.

코드

---

import sys


def dfs(cur):
    if cur == 2:
        return 1
    
    for nxt in range(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] * (n + 1) for _ in range(n + 1)]

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

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

print(ans)