样例过了全wa求调

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

psh18582512217 @ 2024-08-24 12:39:04

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll scc,inst[1000005],ti,n,m,head[1000005],cnt,dfn[1000005],low[1000005];
struct Edge{
    ll next,to;
}e[1000005];
vector<ll> ans[1000005];
void add(ll next,ll to){
    e[++cnt].to=to;
    e[cnt].next=head[next];
    head[next]=cnt;
}
stack<ll> s;
void tarjan(ll x){
    dfn[x]=low[x]=++ti;
    s.push(x);
    inst[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(inst[x]){
            low[x]=min(low[x],low[y]);
        }
    }
        if(dfn[x]==low[x]){
            int y;
            scc++;
            do{
                y=s.top();
                ans[scc].push_back(y);
                s.pop();
            }while(x!=y); 

        } 
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    cout<<scc<<endl;
    for(int i=1;i<=scc;i++){
        sort(ans[i].begin(),ans[i].end());
    }
    sort(ans+1,ans+scc+1);
    for(int i=1;i<=scc;i++){
        for(ll &j : ans[i]){
            cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by sakura_21 @ 2024-09-02 15:03:15

@psh18582512217 你pop那里没有清空标记,我也一样,笑死


|