[BOJ 3295] 단방향 링크 네트워크

문제

---

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

풀이

---

각 노드의 indegree와 outdegree는 최대 1이다.

그리고 최종 가치는 선택된 엣지의 개수와 같다.

이는 곧 최대 이분 매칭의 수와 같다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if (b[nxt] == -1) or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


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

    for __ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        graph[u].append(v)

    b = [-1] * n
    ans = 0
    for i in range(n):
        visit = [0] * n
        ans += dfs(i)

    print(ans)