八段第二课tarjan算法总结

D 构造可达性

解法

首先我们缩点，因为里面都是可达的。

然后我们可以发现，缩完点之后，如果一个点入度为 $0$，那么就说明没有点能到这个点，我们就得答案++。

最后，注意判断 $s$ 所在的点是否有被算入答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

const int N = 2000010;
int h[N],e[N],ne[N],idx;

int n,m,s;
int times=1;
int color[N];
int dfn[N],low[N];
bool vis[N];
int cc=0;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int stk[N];
int top=0;
void dfs(int u)
{
	vis[u]=1;
	dfn[u]=times,low[u]=times++;
	stk[++top]=u;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(!dfn[e[i]])
		{
			dfs(e[i]);
			low[u]=min(low[u],low[e[i]]);
		}
		else if(vis[e[i]])low[u]=min(low[u],dfn[e[i]]);
	}
	if(low[u]==dfn[u])
	{
		int x=-1;
		cc++;
		while(x!=u)
		{
			x=stk[top];
			top--;
			vis[x]=0;
			color[x]=cc;
		}
	}
}
int x[5010],y[5010];
int rd[5010];

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		x[i]=a,y[i]=b;
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) dfs(i);
	}
	for(int i=1;i<=m;i++)
	{
		int a=color[x[i]],b=color[y[i]];
		if(a!=b) rd[b]++;
	}
	int ans=0;
	for(int i=1;i<=cc;i++) if(!rd[i]) ans++;
	if(!rd[color[s]]) ans--;
	cout<<ans;
}