[CF999E]Reachability from the Capital

题目大意：有一个$n$个点$m$条边的有向图，起点$S$，要求你添加最少的边使得$S$可以到达所有点

题解：缩点，答案就是没有入边的强连通分量个数，注意，如果起点$S$所在的强连通块没有入边则不计入答案

卡点：无

C++ Code：

#include <cstdio>

#define maxn 5010

#define maxm 5010

int head[maxn], cnt;

struct Edge {

	int from, to, nxt;

} e[maxm];

inline void add(int a, int b) {

	e[++cnt] = (Edge) {a, b, head[a]}; head[a] = cnt;

}

int DFN[maxn], low[maxn], idx;

int S[maxn], top, res[maxn], CNT;

bool ins[maxn];

inline int min(int a, int b) {return a < b ? a : b;}

void tarjan(int u) {

	DFN[u] = low[u] = ++idx;

	ins[S[++top] = u] = true;

	int v;

	for (int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if (!DFN[v]) {

			tarjan(v);

			low[u] = min(low[u], low[v]);

		} else if (ins[v]) low[u] = min(low[u], DFN[v]);

	}

	if (DFN[u] == low[u]) {

		CNT++;

		do {

			ins[v = S[top--]] = false;

			res[v] = CNT;

		} while (u != v);

	}

}

int n, m, s;

int ind[maxn];

int main() {

	scanf("%d%d%d", &n, &m, &s);

	for (int i = 0, a, b; i < m; i++) {

		scanf("%d%d", &a, &b);

		add(a, b);

	}

	for (int i = 1; i <= n; i++) if (!DFN[i]) tarjan(i);

	for (int i = 1; i <= cnt; i++) {

		int u = res[e[i].from], v = res[e[i].to];

		if (u != v) ind[v]++;

	}

	int ans = 0;

	for (int i = 1; i <= CNT; i++) if (!ind[i]) ans++;

	printf("%d\n", ans - (!ind[res[s]]));

	return 0;

}