92分求助
查看原帖
92分求助
520748
_Ch1F4N_楼主2022/6/5 15:56

挂在第11个点

#include<bits/stdc++.h>
using namespace std;
int dfsn[1000001];//dfs序 
int low[1000001];//最小dfs序 
stack<int> s;//存环 
int vis[1000001],use[1000001];//防重复遍历 
vector<int> road[1000001];//vector存边 
int color[1000001],sum=0;//记录强连通分量数目与每个点最新的强连通分量归属 
int Set[1000001];//记录每个强连通分量内节点数目 
int n,m;
int deep=0;
void paint(int u)
{
	s.pop();
	color[u]=sum;
	Set[sum]++;
	vis[u]=0;
	low[u]=0; 
}
void tanjan(int u)
{
	dfsn[u]=++deep;
	low[u]=deep;
	vis[u]=1;
	use[u]=1;
	//	cout<<"已遍历到"<<u<<"  dfs序"<<dfsn[u]<<endl;
	s.push(u);
	for(int i=0;i<road[u].size();i++)
	{
		int v=road[u][i];
//		cout<<u<<"->"<<v<<endl;
		if(dfsn[v]==0)
		{
			tanjan(v);
			low[u]=min(low[u],low[v]);
		}
	    else
	    {
	    //	cout<<u<<"i"<<endl;
	    	if(vis[v]!=0)
	    	{
	    	low[u]=min(low[u],low[v]);
			}
		}
	}
	if(dfsn[u]==low[u])
	{
	//	cout<<"此时处在"<<u<<endl;
	//	cout<<u<<" "<<dfsn[u]<<" "<<low[u]<<endl;
	//	cout<u<<endl;
	//	cout<<"开始处理"<<endl;
		sum++;
		while(s.top()!=u)
		{
		//	cout<<s.top()<<endl;
	//		cout<<"I"<<endl;
		paint(s.top());
		}
		paint(u);
	//	cout<<"已退栈"<<endl;
//		cout<<Set[sum]<<"点数"<<endl;
	 } 
//	 use[u]=0;
	 return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		road[a].push_back(b);
	}
	for(int i=1;i<=n;i++)
	{
	//	deep=0;
		if(use[i]==0)
		{
			tanjan(i);
		}
	}
	int ans=0;
	for(int i=1;i<=sum;i++)
	{
	//	cout<<Set[i]<<endl;
		if(Set[i]>1)
		ans++;
	}
	cout<<ans;
	return 0;
}

各位dalao帮帮忙。

2022/6/5 15:56
加载中...