欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #490 (Div. 3) E. Reachability from the Capital(tarjan+连通图)

程序员文章站 2022-05-15 14:02:28
...

题目链接
Codeforces Round #490 (Div. 3) E. Reachability from the Capital(tarjan+连通图)
Codeforces Round #490 (Div. 3) E. Reachability from the Capital(tarjan+连通图)
题意:给定一个有向图和顶点s,问给最少给图加几条边使得s能达到图中所有点。
思路:先用tarjan缩点,对于一个连通块内的元素他们肯定是能相互到达的,我们只要判断一下那个连通块的入度为0就说明需要加边。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+1;
vector<int>g[maxn];
int cnt=0,sum=0,dfn[maxn],low[maxn],vis[maxn],a[maxn],b[maxn],num[maxn],out[maxn],ans;
stack<int>s;
void tarjan(int x)
{
	low[x]=dfn[x]=++cnt;
	vis[x]=1;
	s.push(x);
	for(int to:g[x])
	{
		if(!dfn[to]) tarjan(to),low[x]=min(low[x],low[to]);
		else if(vis[to]) low[x]=min(low[x],low[to]);
	}
	if(dfn[x]==low[x])
	{
		++sum;
		int t;
		do{
			t=s.top();
			num[t]=sum;
			vis[t]=0;
			s.pop();
		}while(t!=x);
	}
}
int main()
{
	int n,m,st;
	scanf("%d%d%d",&n,&m,&st);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a[i],&b[i]);
		g[a[i]].push_back(b[i]);
	}
	for(int i=1;i<=n;++i)
	if(!dfn[i]) tarjan(i);
	for(int i=1;i<=m;++i)
	if(num[a[i]]!=num[b[i]]) out[num[b[i]]]++;
	for(int i=1;i<=sum;++i)
	{
		if(out[i]==0&&i!=num[st]) ans++;
	}
	printf("%d\n",ans);
 }