边双连通

/*
 * 求边双连通分量
 * 整体思路就是在图上dfs 并记录时间戳
 * 相较于有向图 只需要注意一条边的两个节点即可
 */






#include <bits/stdc++.h>
#define N 1000010
#define p(a) putchar(a)
using namespace std;
int n,m;

struct edge{
    int to,from,next;
}e[N<<1];int head[N],cntedge=1;//前向星存边,注意边从二开始
void addedge(int from,int to){
    e[++cntedge]={to,from,head[from]};
    head[from]=cntedge;
    swap(from,to);
    e[++cntedge]={to,from,head[from]};
    head[from]=cntedge;
};

int f[N];//记录点是由哪条边访问
int dfn[N],low[N],num,cnt,from[N],cut[N];//dfn：tarjan时间戳   low：tarjan的low num:时间戳 计数器， from[i]:i号节点的连通分量 cnt：连通分量的个数 cut[i]：i号边是否为桥边
int tarjan(int u,int fa){
    dfn[u]=low[u]=++num;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            f[v]=i>>1,tarjan(v,u);
            low[u]=min(low[v],low[u]);
        }else if(v!=fa){//
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(f[u]&&low[u]==dfn[u]){
        cut[f[u]]=1;
    }
}
void dfs(int x,int y){
    from[x]=y;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(!from[v]&&!cut[i>>1]){
            dfs(v,y);
        }
    }
}
signed main(){
    in(n);in(m);
    for(int x,y,i=1;i<=m;i++){
        in(x);in(y);
        addedge(x,y);
    }
    tarjan(1,0);
    for(int i=1;i<=n;i++){
        if(!from[i])dfs(i,++cnt);
    }
    return 0;
}