题解【CF999E】Reachability from the Capital

题面

容易发现一个强连通分量内的点可以互相到达，因此首都最多向每一个强连通分量内连一条边。

于是缩点，原图变成了一个 DAG。

易知只需要向每一个入度为 0 的强连通分量连一条边，这个可以直接统计。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 5003, M = N << 1;

int n, m, s;
int tot, head[N], ver[M], nxt[M];
int dfn[N], low[N], tim, stk[N], tp, id[N], scc_cnt;
bool in_stk[N];
int du[N];

inline void add(int u, int v) {ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;}

void Tarjan(int u)
{
	dfn[u] = low[u] = ++tim, stk[++tp] = u, in_stk[u] = true;
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = ver[i];
		if (!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u])
	{
		++scc_cnt;
		int y = -1;
		do
		{
			y = stk[tp--];
			id[y] = scc_cnt;
			in_stk[y] = false;
		} while (y != u);
	}
}

int main()
{
//	File("");
	n = gi <int> (), m = gi <int> (), s = gi <int> ();
	for (int i = 1; i <= m; i+=1)
	{
		int u = gi <int> (), v = gi <int> ();
		add(u, v);
	}
	for (int i = 1; i <= n; i+=1) if (!dfn[i]) Tarjan(i);
	for (int u = 1; u <= n; u+=1)
		for (int i = head[u]; i; i = nxt[i])
		{
			int v = ver[i];
			if (id[u] != id[v]) ++du[id[v]];
		}
	int cnt = 0;
	for (int i = 1; i <= scc_cnt; i+=1) cnt += (du[i] == 0);
	printf("%d
", cnt - (du[id[s]] == 0));
	return 0;
}