求助~tarjan不开o2会wa?数组开到n会re?
查看原帖
求助~tarjan不开o2会wa?数组开到n会re?
540615
dongyc0301楼主2021/8/4 14:38
#include <bits/stdc++.h> 
using namespace std;
int head[200005],cnt,dfn[200005],low[200005],tot,idx,bj[200005],qwq[200005];
bool in[2000005];
stack <int> s;
struct edge
{
	int ver,next;
}a[200005];
void add(int u,int v)
{
	a[++cnt].ver=v;
	a[cnt].next=head[u];
	head[u]=cnt;
}
void tarjan(int u)
{
	int v;
	dfn[u]=low[u]=++idx;
	s.push(u);
	in[u]=1;
	int i;
	for(i=head[u];i;i=a[i].next)
	{
		v=a[i].ver;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v])
		low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		tot++;
		do
		{
			v=s.top();
			s.pop();
			in[v]=0;
			bj[v]=tot;
		}
		while(u!=v);
	}
 } 
int main()
{
	int n,i,j,ans;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		int t;
		cin>>t;
		while(t!=0)
		{
			if(t!=0)
			add(i,t);
			cin>>t;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(!dfn[i])
		tarjan(i);
	}
	for(i=1;i<=n;i++)
	{
		for(j=head[i];j;j=a[j].next)
		{
			int y=a[j].ver;
			if(bj[i]!=bj[y])
			qwq[bj[y]]=1;
		}
	}
	for(i=1;i<=tot;i++)
	{
		if(!qwq[i])
		ans++;
	}
	
	cout<<ans<<endl;
	return 0;
}
2021/8/4 14:38
加载中...