题目描述

记忆口诀 ：如果一个男生有备胎就绿了他，只有她一个就跟他在一起

Q： state 数组 有什么作用？
A：state 数组 模拟连接的状态。在每一次循环中，加入新的“男生”，如何达到最大匹配呢？最好的情况是，通过重新组合，让这个男生也找到一个人匹配，就可以多配一对。那么此时模拟为：假设所有女生都是可以连接的，那么再进一步计算这个女生原来连接的男生是否有备胎，如果有，那么这个前任和备胎在一起，女生跟新来的男生在一起，以此达到最大匹配的目的。此时在寻找前任男生的备胎的时候，防止再次找到这个女生，将state设置为True，模拟为已找到新欢。意思是，如果除了这个女生，如果前任男生找不到任何一个匹配的，就说明，这个男生没有备胎，这时就让女生仍然跟他在一起，那么这个新遍历到的男生就不能跟这个女生连接。

Python 代码

N = 550
M = 100010
h = [-1]*N
ne = [0]*M
e = [0]*M
idx = 0
match = [0]*N
state = [False]*N
def add(u,v):
    global idx
    ne[idx] = h[u]
    h[u] = idx
    e[idx] = v
    idx += 1 


def find(x):
    head = h[x]
    while head!= -1:
        point_right = e[head]
        if state[point_right] == False:
            state[point_right] = True
            if match[point_right] == 0 or find(match[point_right]) is True:
                match[point_right] = x
                return True
        head = ne[head]
    return False


if __name__ == '__main__':
    n1,n2,m = map(int,input().split())
    for i in range(m):
        u,v = map(int,input().split())
        add(u,v)
    ans = 0 
    for i in range(1,n1+1):
        state = [False]*N
        if find(i) is True:
            ans += 1

    print(ans)