蒟蒻求助tarjan/kel
  • 板块P2002 消息扩散
  • 楼主MSqwq
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/12/25 18:25
  • 上次更新2023/11/5 05:42:13
查看原帖
蒟蒻求助tarjan/kel
247269
MSqwq楼主2020/12/25 18:25

75pts的代码,麻烦各位了

#include<bits/stdc++.h>
using namespace std;
int n,m,elast[100010];
struct qwe{
	int v;
	int next;
}e[1000010];
qwe r[1000010];
int k=0;
void add(int x,int y)
{
	e[++k].next=elast[x];
	e[k].v=y;
	elast[x]=k;
}
long long dfn[100010],low[100010],tot=0,v[100010],scc,be[100010],ans[100010],sum,x,y;
stack<int>s;
void tarjan(int x)
{
	dfn[x]=low[x]=tot++;
	s.push(x);
	v[x]=1;
	int qwe;
	for(int i=elast[x];i;i=e[i].next)
	{
		qwe=e[i].v;
		if(!dfn[qwe])
		{
			tarjan(qwe);
			low[x]=min(low[x],low[qwe]);
		}
		else if(v[qwe])
		{
			low[x]=min(low[x],dfn[qwe]);
		}
	}
	if(low[x]==dfn[x])
	{
		scc++;
		do
		{
			qwe=s.top();
			s.pop();
			v[qwe]=0;
			be[qwe]=scc;
		}while(x!=qwe);
	}
}

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i);
//	for(int i=1;i<=n;i++)cout<<be[i]<<" ";
//	cout<<endl;

	for(int i=1;i<=n;i++)
	{
		for(int j=elast[i];j;j=e[j].next)
		{
			int k=e[j].v;
			if(be[i]!=be[k])
			{
				ans[be[k]]=1;
			}
		}
	} 
	for(int i=1;i<=scc;i++)if(ans[i]==0)sum++;
	cout<<sum;
}
2020/12/25 18:25
加载中...