第一次打tarjan,样例过不了。求助
查看原帖
第一次打tarjan,样例过不了。求助
615236
FF_pigeon楼主2023/5/4 22:35

感谢进来

过了1,14,15三个点

请求支援

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int M=5e5;
int n,m,a,b,ans,cnt,no,tot;
int head[N],vs[N],vis[N],dfn[N],low[N],point[N],rst[N];
stack<int>s;
int read()
{
    char ch=getchar();
    int a=0,x=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') x=-x;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        a=(a<<3)+(a<<1)+(ch-'0');
        ch=getchar();
    }
    return a*x;
}
struct Edge
{
	   int u,v,w;
}e[M+N];
struct dot
{
	   int nxt,to;
}g[M];//Òªµ÷
void add(int u,int v,int w)
{
	 e[no].u=u;
	 e[no].v=v;
	 e[no].w=w;
	 g[no].to=v;
	 g[no].nxt=head[u];
	 head[u]=no++;
}
void tarjan(int x)
{
	vis[x]=1;
	dfn[x]=low[x]=++cnt;
	s.push(x);
	vs[x]=1;
	for(int i=head[x];i;i=g[i].nxt)
	{
		int v=g[i].to;
		if(vis[v]==0)
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else
		{
			if(vs[v]==1)
			{
				low[x]=min(low[x],dfn[v]);
			}
		}
	}
	if(low[x]==dfn[x])
	{
		tot++;
		int tmp;
		while(s.top()!=x)
		{
			tmp=s.top();
			s.pop();
			vs[tmp]=0;
			point[tmp]=tot;
		}
		tmp=s.top();
		s.pop();
		vs[tmp]=0;
		point[tmp]=tot;
	}
	return;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		a=read();
		b=read();
		add(a,b,1);
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)tarjan(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=g[j].nxt)
		{
			int v=g[i].to;
			if(point[i]!=point[v])
			{
				rst[point[v]]=1;
			}
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(rst[i]==0);
		{
			ans++;
		}
	}
	cout << ans;
	return 0;
}
2023/5/4 22:35
加载中...