萌新球调tarjan /kel
查看原帖
萌新球调tarjan /kel
183954
MC小萌新楼主2021/9/25 21:26

可以通过样例,自己造的数据也可,但提交全WA/kk

#include <iostream>
using namespace std;
int n,m,u,v,dfn[11000],stack[11000],low[11000],sze,start[11000],t,cnt,belong[11000];
bool ins[11000],vis[11000],vis1[11000];
struct edge{
    int e,next;
}ed[110000];
void add(int u,int v,int k){
    ed[k].next=start[u];
    start[u]=k;
    ed[k].e=v;
}
void dfs(int now){
    dfn[now]=low[now]=++t;
    vis1[now]=1;
    stack[++sze]=now;
    ins[now]=1;
    for(int i=start[now];i!=0;i=ed[i].next){
        int e=ed[i].e;
        vis1[e]=1;
        if(!dfn[e]){
            dfs(e);
            low[now]=min(dfn[now],low[e]);
        }
        else{
            if(ins[e]){
                low[now]=min(low[now],dfn[e]);
            }
        }
    }
    if(dfn[now]==low[now]){
        ++cnt;
        while(stack[sze]!=now){
            belong[stack[sze]]=cnt;
            ins[stack[sze--]]=0;
            vis1[stack[sze]]=1;
        }
        belong[stack[sze]]=cnt;
        vis1[stack[sze]]=1;
        ins[stack[sze--]]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        add(u,v,i);
    }
    dfs(1);
    for(int i=1;i<=n;++i)
        if(vis1[i]==0)
            ++cnt;
    cout<<cnt<<endl;
    for(int i=1;i<=n;++i){
        
        if(!vis[i]){
            vis[i]=1;
            cout<<i<<" ";
            for(int j=i+1;j<=n;++j){
                if(belong[j]==belong[i]){
                    cout<<j<<" ";
                    vis[j]=1;
                }
            }
            cout<<endl;
        }
    }
    return 0;
}
2021/9/25 21:26
加载中...