萌新求助 WA#11 #12
查看原帖
萌新求助 WA#11 #12
642481
Esawkm楼主2022/10/24 16:51
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
bool inzhan[N];
int n,m,x,y,dep,cnt,top,rp,from[N],xiayige[N],to[N],head[N],dfn[N],low[N],zhan[N],abc[N];;;;;
int add(int x,int y)
{
    cnt++;
    to[cnt]=y;
    cnt[xiayige]=head[x];
    head[x]=cnt;
}
void tajian(int u)
{
	dep++;
    dfn[u]=dep;
	low[u]=dep;
    zhan[++top]=u;
	inzhan[u]=1;
    for(int i=head[u];i;i=xiayige[i])
    {
        int t=to[i];
        if(inzhan[t]) 
		low[u]=min(low[u],dfn[t]);
        else 
		if(dfn[t]!=1) 
		{
		 tajian(t);
		 low[u]=min(low[u],low[t]);
        }
	}
    if(low[u]==dfn[u])
    {
        rp++;
		abc[u]=rp;
        int ans=1;
        for(int fd=1;zhan[top]!=u;top--)
        {
            inzhan[zhan[top]]=0;
            abc[zhan[top]]=rp;
            ans++;
        }
        inzhan[u]=0;
		top--;
        if(ans==1) 
		rp--;
    }
    
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
     cin>>x>>y;
	 add(x,y);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i]) 
	tajian(i);
    cout<<rp;
    return 0;
}
2022/10/24 16:51
加载中...