萌新第一次写缩点!25分求助!
查看原帖
萌新第一次写缩点!25分求助!
920406
违规用户名920406楼主2024/12/18 20:49
//tarjan 缩点后变成有向无环图,输出入度为 0 的点个数

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,m,x,y,tim,tot,ans,dfn[N],low[N],instk[N],id[N],rd[N];
vector<int> v[N],stk;
void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    stk.push_back(x);
    instk[x]=1;
    for(auto i:v[x])
    {
        if(!dfn[i])
        {
            tarjan(i);
            low[x]=min(low[x],low[i]);
        }
        else if(instk[i])
            low[x]=min(low[x],dfn[i]);
    }
    if(low[x]==dfn[x])
    {
        id[x]=++tot;
        while(stk.back()!=x)
        {
            id[stk.back()]=tot;
            instk[stk.back()]=0;
            stk.pop_back();
        }
        instk[stk.back()]=0;
        stk.pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(auto j:v[i])
            if(id[j]!=id[i])
                rd[j]++;
    for(int i=1;i<=tot;i++)
        if(!rd[i])
            ans++;
    cout<<ans;
    return 0;
}
2024/12/18 20:49
加载中...