强连通分量+缩点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> g[N],id[N];
int n,m;
int low[N],dfn[N],st[N],instack[N],belong[N],in[N],tot=0,cnt=0,scc=0;
void tarjan(int x)
{
    int v;
    low[x]=dfn[x]=++tot;
    st[++cnt]=x;
    instack[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        v=g[x][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(instack[v])
        {
            low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x])
    {
        scc++;
        do{
            v=st[cnt--];
            instack[v]=0;
            belong[v]=scc;
            id[scc].push_back(v);
        }while(x!=v);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(dfn,0,sizeof dfn);
    cin>>n>>m;
    int u[N],v[N];
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        g[u[i]].push_back(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
    for(int i=1;i<=m;i++)//缩点
    {
        if(belong[u[i]]==belong[v[i]])continue;
        in[belong[v[i]]]++;
    }
    for(int i=1;i<=scc;i++)
        sort(id[i].begin(),id[i].end());
    int sum=0,ans[N];
    for(int i=1;i<=scc;i++)
    {
        if(!in[i])
        {
            sum++;
            ans[sum]=id[i][0];
        }
    }
    printf("%d\n",sum);
    for(int i=1;i<=sum;i++)
    {
        printf("%d ",ans[i]);
    }
}

打赏