P2812 校园网络 [USACO]Network of Schools - 洛谷
给定一个有向图， \(A \rarr B\) 表示 \(A\) 可以给 \(B\) 发送软件。
- 问：最少需要给多少学校发送软件可以让所有学校收到
- 问：最少加几条边，可以给任意一所学校发送软件使全图可以收到
在有向图中，如果节点之间形成了环（强连通分量） ，那么其中一个可以收到，环内所有节点都可以收到。
所以我们只需要对原图进行 缩点 成一个 DAG 。那么第一问就变成了：入度为 \(0\) 的节点有多个。第二问的意思变为再加几条边可以使图变为强连通图。
变成强连通图的条件是消除所有源点和汇点，假如度为 \(0\) 的点和入度为 \(0\) 的点的个数为 \(P,Q\) ，为了用最少得边将其串联起来，我们需要为其匹配的边为 \(\max(P,Q)\) 。
特判，如果缩点后 \(scc=1\) 那么该图已经是强连通图，此时 \(P=Q=1\) 但是，应该输出 \(0\) 不需要再加边了。
如果想要输出具体的边匹配情况，需要用到 二分图最大匹配 来寻找尽可能多的独立路径因为一般的循环配对法可能会生成小强连通环。进阶题目参考 QOJ #15056 JSOI 2014 强连通图 这道题目需要你严格的匹配源点和汇点。
具体 Python 代码如下
import sys
sys.setrecursionlimit(100000)
if 1:inp = lambda: sys.stdin.readline().strip()II = lambda: int(inp())MII = lambda: map(int, inp().split())LII = lambda: list(MII())Max = lambda x, y: x if x > y else yMin = lambda x, y: x if x < y else ydef main():n = II()g = [[]]for _ in range(n):v = LII()g.append(v[:-1])dfn = [-1] * (n + 1)low = [-1] * (n + 1)st = []inst = [False] * (n + 1)timer = 1scc = 0scc_id = [-1] * (n + 1)def tarjan(x):nonlocal timer, sccdfn[x] = low[x] = timertimer += 1st.append(x)inst[x] = Truefor y in g[x]:if dfn[y] == -1:tarjan(y)low[x] = Min(low[x], low[y])elif inst[y]:low[x] = Min(low[x], dfn[y])if dfn[x] == low[x]:while True:cur = st.pop()inst[cur] = Falsescc_id[cur] = sccif cur == x:breakscc += 1for i in range(1, n + 1):if dfn[i] == -1:tarjan(i)din = [0] * sccdout = [0] * sccfor u in range(1, n + 1):for v in g[u]:if scc_id[u] != scc_id[v]:din[scc_id[v]] += 1dout[scc_id[u]] += 1a = sum(1 for i in range(scc) if din[i] == 0)b = sum(1 for i in range(scc) if dout[i] == 0)print(a)print(Max(a, b) if scc != 1 else 0)if __name__ == "__main__":main()