Jisoo

tarjan求割边

对于一条$(u,v)$，如果他是割边，那么v子树中一定有一个点s$low_s>dfn_u$

然后改造一下搜索函数

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
int n,m;
int be[1000001];
int sc;
stack<int> s;
int x,y;;
int low[100001];
int df[100001];
int dfn;
int head[1000001];
struct e{
    int to;
    int ne;
}ed[1000001];
int edd[150][150];
int siz[100001];
int p;
void add(int x,int y){
    ed[++p].to=y;
    ed[p].ne=head[x];
    head[x]=p;
}
int du[100001];
void dfs(int x,int fa){
    ++dfn;
    low[x]=df[x]=dfn;
    s.push(x);
    for(int i=head[x];i;i=ed[i].ne){
        int v=ed[i].to;
        if(v==fa){
            continue;
        }
        if(df[v]){
            low[x]=min(low[x],df[v]);
        }else{
            dfs(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>df[x]){
                edd[x][v]=edd[v][x]=1;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;++i){
        if(!df[i]){
            dfs(i,i);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(edd[i][j]){
                printf("%d %dn",i,j);
            }
        }
    }
    return 0;
}