全WA求助
查看原帖
全WA求助
757902
lizerui520楼主2022/8/24 11:06

大佬们帮我康康吧

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
vector<int> e[N];
int dfn[N],low[N],tot;
int zhan[N],zp[N];
int siz[N],scc[N],top,cnt,ans;
void l(int u)
{
	dfn[u]=low[u]=++tot;
	zhan[++top]=u;
	zp[u]=1;
	for(int y:e[u])
	{
		if(!dfn[u])
		{
			l(y);
			low[u]=min(low[u],low[y]);
		}
		else if(zp[y])
		{
			low[u]=min(dfn[u],low[y]);
		}
	}
	if(dfn[u]==low[u]){
		int y;++cnt;
		do{
			y=zhan[top--];
			zp[y]=0;
			++siz[cnt];
		}while(y!=u);
	}
}
int main()
{
	int a,b;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		e[a].push_back(b);
		
	}
	for(int i=1;i<=n;i++)
    {
        if (!dfn[i]) l(i);
    }
    for(int i=1;i<=cnt;i++){
    	if(siz[i]>1)ans++;
	}
    cout<<ans;
}
2022/8/24 11:06
加载中...