救救孩子 哪位大佬帮忙看一下这个 48分代码 WA
查看原帖
救救孩子 哪位大佬帮忙看一下这个 48分代码 WA
414220
2019lzh楼主2023/1/29 21:08
#include<bits/stdc++.h>
using namespace std;
int n,m,xx,yy,sum,num=0,jishu=1;
stack <int> qq;  
bool visit[10001];
bool instack[10001];
int dfn[10001],vis[10001];
bool a[10001][10001];
void tarjan(int x)
{
	//cout<<"tarjan "<<x<<endl<<endl;
	
	num++;
	vis[x]=dfn[x]=num;
	qq.push(x);
	//cout<<"qq.top "<<qq.top()<<endl;
	instack[x]=1;
	for(int i=1;i<m;i++)
	{
		if(a[x][i]==1)
		{
			if(visit[i]!=1)
			{
				visit[i]=1;
				tarjan(i);
				vis[x]=min(vis[x],vis[i]);
			//	cout<<"vis[x]=min(vis[x],vis[i])1  "<<x<<i<<"vis[]"<<x<<" "<<vis[x]<<endl;//测试 
			}
			else if (instack[i]==1); 
				vis[x]=min(vis[x],vis[i]);
			//	cout<<"vis[x]=min(vis[x],vis[i])2  "<<x<<i<<"vis[]"<<x<<" "<<vis[x]<<endl;//测试 
		} 
	}
	if(dfn[x]==vis[x]) //没用,执行出栈操作 
	{
		int jishu=1;
		//cout<<qq.top()<<"第31行pop1"<<endl;//测试 
		while(qq.top()!=x) 
		{
			jishu++;
		//	cout<<jishu<<"  "<<qq.top()<<"第36行pop2"<<endl;//测试 
			instack[qq.top()]=0;
			qq.pop();
			
		}
		instack[qq.top()]=0;
		qq.pop();
		if(jishu>=1) sum++;
	}
	return ;
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>xx>>yy;
		a[xx][yy]=1;//存图 
	}
	for(int i=1;i<=m;i++)
	{
		if(visit[i]==0)
		{
		//	cout<<i;//test
			visit[i]=1;
		//	cout<<"第61行tarjan"<<i<<endl;//测试 
			tarjan(i);
		
		}
	}
//	cout<<"输出正常"; 
	cout<<sum;
	return 0;
}
2023/1/29 21:08
加载中...