tarjan写法wa一个点，求调

struct_cym @ 2023-10-13 18:12:21

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
vector<int>edge[N];
int dfn[N],low[N];
int st[N];//栈
int co[N]; 
int flag[N];
int num,tops,col;
void tarjan(int u){
    dfn[u]=low[u]=num++;
    st[++tops]=u;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!co[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        co[u]=++col;
        while(st[tops]!=u){
            co[st[tops]]=col;
            --tops;
        }
        --tops;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    cout<<col<<endl;
    for(int i=1;i<=n;i++){
        if(flag[i]){
            continue;
        }
        flag[i]=1;
        cout<<i<<" ";
        for(int j=i+1;j<=n;j++){
            if(co[j]==co[i]){
                flag[j]=1;
                cout<<j<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

by Sincerin @ 2023-10-13 18:37:04

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
vector<int>edge[N];
int dfn[N],low[N];
int st[N];//栈
int co[N]; 
int flag[N];
int num,tops,col;
void tarjan(int u){
    dfn[u]=low[u]=++num;////////////////////////
    st[++tops]=u;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!co[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        co[u]=++col;
        while(st[tops]!=u){
            co[st[tops]]=col;
            --tops;
        }
        --tops;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    cout<<col<<endl;
    for(int i=1;i<=n;i++){
        if(flag[i]){
            continue;
        }
        flag[i]=1;
        cout<<i<<" ";
        for(int j=i+1;j<=n;j++){
            if(co[j]==co[i]){
                flag[j]=1;
                cout<<j<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

by Sincerin @ 2023-10-13 18:40:20

dfn[u]=low[u]=num++;其实是等价于dfn[u]=low[u]=num; num++;的，也就是说第一个点的dfn和low都会被标记为0。

by Sincerin @ 2023-10-13 18:42:05

tarjan内部第一行改为++num谢谢喵

by struct_cym @ 2023-10-13 18:45:38

@Sincer 谢谢啦，关注一下你