G002 强连通分量 Tarjan算法 CF999E Reachability from the Capital

CF999E Reachability from the Capital - CodeForces

给定一个有向图和一个节点 \(s\) ，问最少加多少条边可以使 \(s\) 可以到达图中所有的点（ \(s\) 可以到达自身）

考虑缩点，缩点后源点一定被无法到达，所以我们需要统计源点的个数。

特判，当 \(s\) 在其中一个源点中时，这时应该少加一条边。

import sys
sys.setrecursionlimit(10000)
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, m, s = MII()g = [[] for _ in range(n + 1)]for _ in range(m):u, v = MII()g[u].append(v)dfn = [-1] * (n + 1)low = [-1] * (n + 1)st = []inst = [False] * (n + 1)scc_id = [-1] * (n + 1)scc = 0timer = 1def 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] * sccfor u in range(1, n + 1):for v in g[u]:if scc_id[u] != scc_id[v]:din[scc_id[v]] += 1cnt = sum(1 for i in range(scc) if din[i] == 0)print(cnt - 1 if din[scc_id[s]] == 0 else cnt)if __name__ == "__main__":main()