样例过了全WA,很多大佬都找不出bug,求神犇调题

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

SZbr @ 2021-07-15 19:28:23

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

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
int n,m,tot,head[10010],bel[10010],totb,dfn[10010],low[10010],cnt;
bool tost[10010],vis[10010];
stack<int> st;
vector<int> vct[10010];
struct node{
    int v,next;
}edge[100010];
void make(int u,int v){
    edge[++tot].v=v;
    edge[tot].next=head[u];
    head[u]=tot;
}
void tarjian(int x){
    st.push(x);
    tost[x]=true;
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=edge[i].next){
        if(!dfn[edge[i].v]){
            tarjian(edge[i].v);
            low[x]=min(low[x],low[edge[i].v]);
        }
        else if(tost[x]){
            low[x]=min(low[x],dfn[edge[i].v]);
        }
    }
    if(low[x]==dfn[x]){
        totb++;
        while(st.top()^x){
            bel[st.top()]=totb;
            vct[totb].push_back(st.top());
            tost[st.top()]=false;
            st.pop();
        }
        st.pop();
        bel[x]=totb;
        vct[totb].push_back(x);
        tost[x]=false;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        make(u,v);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i]){
            tarjian(i);
        }
    }
    printf("%d\n",totb);
    for(int i=totb;i>=1;--i){
        sort(vct[i].begin(),vct[i].end());
//      int j;
//      for(auto j:vct[i]){
//          printf("%d ",j);
//      }
//      printf("\n");
    }
    for(int i=1;i<=n;++i){
        if(vis[i]) continue;
        int j;
        for(auto j:vct[bel[i]]){
            printf("%d ",j);
            vis[j]=true;
        }
        printf("\n");
    }
    return 0;
}

by wheneveright @ 2021-07-15 19:32:12

请求开放数据下载 /fn

@SSerxHs


by cyhyyds @ 2021-07-15 19:50:35

数组开太小?


by FoXreign @ 2021-07-19 15:04:30

你的tarjan算法中在枚举每条边时的else if判断条件错了,这时应该是判断edge[i].v是否在栈中,而不是当前节点x


by yizcdl2357 @ 2021-07-28 21:10:14

tarjian好评


|