rt,SCC求调试

B3609 [图论与代数结构 701] 强连通分量

Isharmla @ 2023-10-13 17:10:45

求调试。

// Problem: B3609 [图论与代数结构 701] 强连通分量
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3609
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define F(i,a,b) for(int i=a;i<=b;i++)

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}

const int N=4e5+5;

int head[N],nxt[N],to[N],tot;

inline void AddEdge(int u,int v){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}   
int cnt,n,m,stk[N],tp,number_scc,dfn[N],low[N];//栈元素,栈顶,SCC的数量
bool In_stk[N];//是否在栈里面
vector<int> S[N];
void Tarjan(int u){
    dfn[u]=low[u]=(++cnt);
    stk[++tp]=u;In_stk[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        if(!dfn[to[i]]){
            Tarjan(to[i]);
            low[u]=min(low[u],low[to[i]]);
        }else if(In_stk[to[i]]==1){
            low[u]=min(low[u],dfn[to[i]]);
        }
    }
    if(dfn[u]==low[u]){
        number_scc++;
        while(stk[tp]!=u){
            In_stk[tp]=0;
            S[number_scc].push_back(stk[tp]);
            tp--;
        }
        In_stk[tp]=0;
        S[number_scc].push_back(u);
        tp--;
    }
}
bool cmp(vector <int> a, vector <int> b) {
    return *a.begin() < *b.begin();
}
signed main(){
    n=read(),m=read();     
    for(int i=1,u,v;i<=m;i++){
        u=read(),v=read();
        AddEdge(u,v);
    }
    F(i,1,n){
        if(!dfn[i]) Tarjan(i);
    }
    for (int i=1;i<=number_scc;i++)
        sort(S[i].begin(),S[i].end());
    sort(S+1,S+1+number_scc,cmp);
    cout<<number_scc<<endl;
    F(i,1,number_scc){
        //sort(S[i].being(),S[i].end());
        F(j,0,S[i].size()-1) cout<<S[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

by UYHW @ 2023-10-13 17:47:59

@Isharmla In_stk[tp]=0 -> In_stk[stk[tp]]


|