求助

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

Anatomix @ 2023-06-23 11:30:06

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
inline int read(){
    int sum=0,check=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
            check=-1;
        }
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        sum=(sum<<1)+(sum<<3)+(ch^48);
        ch=getchar();
    }
    return sum*check;
}
int n,m;
int cnt,Time,len,CNT;
int root[N],flag[N];
int head[N],dfn[N],low[N],Stack[N];
bool instack[N];
vector<int> ans[N];
struct node{
    int to,next;
}edge[10*N];
void addedge(int from,int to){
    cnt++;
    edge[cnt].to=from;
    edge[cnt].next=head[from];
    head[from]=cnt;
}   
void tarjan(int n){
    dfn[n]=low[n]=++Time;
    Stack[++len]=n;
    instack[n]=true;
    for(int i=head[n];i;i=edge[i].next){
        int temp=edge[i].to;
        if(!dfn[temp]){
            tarjan(temp);
            low[n]=min(low[n],low[temp]);
        }
        else if(instack[temp]){
            low[n]=min(low[n],low[temp]);
        }
    }
    if(dfn[n]==low[n]){
        CNT++;
        while(len>0){
            int temp=Stack[len];
            len--;
            instack[temp]=false;
            ans[CNT].push_back(temp);
            root[temp]=CNT;
            if(temp==n){
                break;
            }
        }
    }
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int temp1=read(),temp2=read();
        addedge(temp1,temp2);   
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }
    printf("%lld\n",CNT);
    for(int i=1;i<=CNT;i++){
        sort(ans[i].begin(),ans[i].end());
    }
    for(int i=1;i<=n;i++){
        if(flag[root[i]]){
            continue;
        }
        flag[root[i]]=true;
        for(int j=0;j<ans[root[i]].size();j++){
            printf("%lld ",ans[root[i]][j]);
        }
        printf("\n");
    }
    return 0;
}

全错样例都过不了


by technopolis_2085 @ 2023-06-23 11:40:34

建边建错了。

edge[cnt].to=from;

应该改为:

edge[cnt].to=to;

by technopolis_2085 @ 2023-06-23 11:42:27

试过了,改完了就可以AC。


by Anatomix @ 2023-06-23 11:44:27

@past_tense 感谢大佬 关注已点


|