不开O2 全TLE 开了O2全WA 自己的数据和样例都能过 求调

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

秀……虚空 @ 2023-09-06 16:15:06

求调


#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int vis[maxn];
int dfn[maxn],low[maxn],num,n,m;
int ver[maxn],Next[maxn],head[maxn],tot,top,_stack[maxn],ins[maxn],cnt,c[maxn];
vector<int> scc[maxn];
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++num;
    _stack[++top]=x,ins[x]=1;
    for(int i=head[x];i;i=Next[i]){
        if(!dfn[ver[i]]){
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if(ins[ver[i]]){
            low[x]=min(low[x],dfn[ver[i]]);
        }
    }
    if(dfn[x]==low[x]){
        cnt++;int y;
        do{
            y=_stack[top--],ins[y]=0;
            c[y]=cnt,scc[cnt].push_back(y);
        }while(x!=y);
    }
}
int vc[maxn],nc[maxn],hc[maxn],tc;
void add_c(int x,int y){
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
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);
    }
    for(int i=1;i<=cnt;i++){
        sort(scc[i].begin(),scc[i].end());
    }
    memset(vis,0,sizeof(vis));
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++){
        if(vis[c[i]])continue;
        vis[c[i]]=1;
        for(int j=0;j<scc[c[i]].size();j++){
            cout<<scc[c[i]][j]<<' ';
        }
        cout<<endl;
    }
    /*
    for(int x=1;x<=n;x++){
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(c[x]==c[y])continue;
            add_c(c[x],c[y]);
        }
    }*/

    return 0;
}

|