题目描述

Intercept在玩一种游戏，游戏中有 n 座城市，城市之间用单向的道路连接，形式化地说，n 座城市构成了一个有向无环图。Intercept可以控制一些毁灭机器人，对于每一个毁灭机器人，Intercept可以让它从任意一座城市出发，沿着道路以任意的路径移动，在任意一座城市停止。毁灭机器人每经过一座城市，这座城市都会被占领。但是，任意两个毁灭机器人不能经过同一座城市，因为毁灭机器人也会消灭毁灭机器人。Intercept想知道，他至少需要准备多少毁灭机器人，才能占领所有城市。

注意：因为Intercept可以在所有点都设置一个毁灭机器人，所以一定是有解的。

题目分析

最小不相交路径覆盖

这是一道求最小不相交路径覆盖的题，$最小不相交路径覆盖 = n-二分图最大匹配$。

我们首先假设所有点上都有一个破坏机器人，这是一个可行解，但不是最优解。现在我们尝试优化答案：

1. 我们可以在两个点间连一条边，表示机器人可行意味着这两个点可以只用一个机器人占领，这样显然可得连的边越多，机器人越少，答案越优。
2. 那么要求不相交对于我们连边来说有什么限制吗？只需保证每一个点最多只有一条出边，一条入边。
3. 我们已经能看出二分图匹配的模型了，我们把每一个点拆成两个点（出点，入点）那么我们就可以用二分图最大匹配来求出满足 2 条件的能连的最大边数(左集合为出点，右集合为入点)。答案显然可得为 $n-最大匹配$

最小相交路径覆盖

接下来我们谈谈最小相交路径覆盖怎么用二分图最大匹配来求：

1. 其实最小不相交路径覆盖意味着$1->2,2->4$等同余存在$1->4$。
2. 那么我们就可以把这些可达的点都加上对应的边，然后做一遍最小不相交路径覆盖即可
3. 那么我们怎么实现加边呢，你可能已经想到了，跑一边传递闭包即可。

python code(最小不相交路径覆盖):

import sys
input = sys.stdin.readline

def dfs(x):
    for y in g[x]:
        if vis[y]: continue
        vis[y] = 1
        if not link[y] or dfs(link[y]):
            link[y] = x
            return 1
    return 0

n,m = map(int, input().split())
g = {i:[] for i in range(n+n+1)}
for i in range(m):
    x,y = map(int, input().split())
    g[x].append(y+n)

link = [0]*(n+n+1)
ans = 0
for i in range(1,n+1):
    vis = [0]*(n+n+1)
    if dfs(i): ans += 1
print(n - ans)