提出 #73667061

---

ソースコード 拡げる

import sys; I = sys.stdin.readline
II, FL = lambda: int(I()), lambda: map(int, I().split())
FLL = lambda: [*FL()]; FLT = lambda: tuple(FL())
R, E, P, L, F, INF = range, enumerate, print, len, filter, float('inf')
S, RS, KS = sorted, lambda it: S(it, reverse=True), lambda it, f: S(it, key=f)
DEC, INC, YN = lambda x: x-1, int(1).__add__, lambda y: P('Yes' if y else 'No')
CDIV = lambda n, a: -(-n // a)
import os; LOCAL = "INSIDE_EMACS" in os.environ
D = lambda *args, **kwargs: P('DBG:', *args, **kwargs) if LOCAL else None


def kuhn(n_left, n_right, adj):
    """
    n_left  = number of vertices in left part U (0..n_left-1)
    n_right = number of vertices in right part V (0..n_right-1)
    adj[u]  = list of neighbors v in V
    """
    match_to = [-1] * n_right  # match_to[v] = u, or -1 if v unmatched

    def dfs(u):
        if used[u]:
            return False
        used[u] = True
        for v in adj[u]:
            if match_to[v] == -1 or dfs(match_to[v]):
                match_to[v] = u
                return True
        return False

    match_size = 0
    for u in range(n_left):
        used = [False] * n_left
        if dfs(u):
            match_size += 1

    return match_size

for _ in R(II() if LOCAL else 1):
    n, m = FL(); g = [[*map(DEC, FL())][1:] for _ in R(n)]
    P(kuhn(n, m, g))

提出情報

ジャッジ結果