*玄关*24pts马风很好求调!!
查看原帖
*玄关*24pts马风很好求调!!
1399216
_Gloaming_楼主2024/8/15 16:58
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+100;
struct node
{
    int u,v;
}e[N*5];
int n,m,ans=0,cnt=0,col=0;
int h[N],dfn[N],low[N],sd[N],k=0,scc[N],sccum[N],out[N];//top(手写栈)
bool f[N];
stack <int> s;
void add(int u,int v)
{
    ++cnt;
    e[cnt].u=h[u];
    e[cnt].v=v;
    h[u]=cnt;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++k;
    f[x]=1;//已经遍历过了
    s.push(x);
    for(int i=h[x];i;i=e[i].u)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(f[v])
            low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x])
    {
        int q;
        scc[++col]=x;
        while(x!=q)
        {
            q=s.top();s.pop();
            f[q]=0;
            sd[q]=x;
            sccum[x]++;
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(low,0x3f,sizeof(low));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=m;i++)
    {
        int x=sd[e[i].u];
        int y=sd[e[i].v];
        if(x!=y)
            out[x]++;
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<sd[i]<<" "<<out[i]<<"\n";
    // }
    for(int i=1;i<=col;i++)
    {
        //cout<<scc[i]<<" sdihf "<<out[scc[i]]<<" "<<sccum[scc[i]]<<"\n";
        if(out[scc[i]]==0)
            ans+=sccum[scc[i]];
    }
    cout<<ans;
}
2024/8/15 16:58
加载中...