全WA求助

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

一只大龙猫 @ 2021-08-29 09:09:06

样例已过,但是全都WA了。Tarjan 算法,链式前向星存图。

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n,m,u,v,tot,head[1000001],dfn[1000001],low[1000001],index_,cnt,scc[1000001];
bool inst[1000001],vis[1000001];
struct edge{
    int u,v,next;
}g[1000001];
stack<int> st;
void addedge(int u,int v){
    g[++tot].u=u;
    g[tot].v=v;
    g[tot].next=head[u];
    head[u]=tot;
    return;
}
void tarjan(int u) {
    dfn[u]=low[u]=++index_;
    st.push(u);
    inst[u]=1;
    for(int i=head[u];i!=-1;i=g[i].next){
        int v=g[i].v;
        if(dfn[v]==-1) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(inst[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(dfn[u]==low[u]){
        cnt++;
        int v;
        do{
            v=st.top();
            st.pop();
            scc[v]=cnt;
            inst[v]=0;
        }while(u!=v);
    }
    return;
}
int main(){
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    memset(dfn,-1,sizeof(dfn));
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        addedge(u,v);
    }
    tarjan(1);
    cout<<cnt<<endl; 
    for(int i=1;i<=n;i++){
        if(vis[scc[i]])continue;
        vis[scc[i]]=1;
        for(int j=1;j<=n;j++){
            if(scc[j]==scc[i])cout<<j<<" ";
        }
        cout<<endl;
    }
    return 0;
}

by Exber @ 2021-08-29 09:16:46

@一只大龙猫 不保证图联通


by 一只大龙猫 @ 2021-08-29 09:19:04

@lovely_ckj A了,谢谢


|