tarjan 全wa求调

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

huta0 @ 2024-01-20 10:01:19

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define a_all a.begin(),a.end()
using namespace std;
typedef long long ll;
int n,m;
int dfn[10010],low[10010];
int siz[10010],cnt,tot,top;
int stk[10010],instk[10010];
bool vis[10010];
struct edge {
    int v;
};
vector<edge> e[10010];
vector<vector<int>> ans;
void tarjan(int x) {
    dfn[x]=low[x]=++tot;
    stk[++top]=x,instk[x]=1;
    vis[x]=1;
    for(edge ed:e[x]) {
        if(!dfn[ed.v]) {
            tarjan(ed.v);
            low[x]=min(low[x],low[ed.v]);
        } else if(instk[ed.v])
            low[x]=min(low[x],dfn[ed.v]);
    }
    if(dfn[x]==low[x]) {
        int y; ++cnt;
        vector<int> v;
        do {
            y=stk[top--];
            instk[y]=0;
            v.push_back(y);
            //cout<<y<<" ";
            siz[cnt]++;
        } while(y!=x);
        //cout<<endl;
        sort(v.begin(),v.end());
        ans.push_back(v);
    }
}
int main() {
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    memset(stk,0,sizeof(stk));
    memset(instk,0,sizeof(instk));
    memset(siz,0,sizeof(siz));
    memset(vis,0,sizeof(vis));
    rep(i,1,m) {
        int a,b;
        cin>>a>>b;
        e[a].push_back({b});
    } 
    rep(i,1,n) {
        if(!vis[i]) tarjan(i);
    }
    cout<<ans.size()<<endl;
    for(int i=ans.size()-1;i>=0;i--) {
        for(int k : ans[i])
           cout<<k<<" ";
        cout<<endl;   
    }
    return 0;
}

by chensiyu1 @ 2024-04-16 16:29:50

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,u,v;
int dfs_clock;
int dfn[N];
vector<int> G[N];
stack<int> st;
int scc_cnt;
int sccno[N];
vector<int> scc[N]; 
int low[N];
bool vis[N];
void tarjan(int u){
    low[u]=dfn[u]=++dfs_clock;
    st.push(u);
    for(auto v:G[u]){
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!sccno[v]){
            low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        scc_cnt++;
        int x;
        do{
            x=st.top();
            st.pop();
            sccno[x]=scc_cnt;
            scc[scc_cnt].push_back(x);
        }while(x!=u);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    cout<<scc_cnt<<endl;
    for(int i=1;i<=n;i++){
        int idx=sccno[i];
        if(!vis[idx]){
            vis[idx]=1;
            sort(scc[idx].begin(),scc[idx].end());
            for(auto v:scc[idx]){
                cout<<v<<" ";
            }
            cout<<endl;
        }
    } 
    return 0;
}

可AC!!!

|