tarjan边双联通

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],cnt;
    void ini(int n){
        for(int i=0;i<=n;i++) head[i]=-1;
        cnt=-1;
    }
    void add_edge(int u,int v){
        edge[++cnt]=star{v,head[u]};
        head[u]=cnt;
        edge[++cnt]=star{u,head[v]};
        head[v]=cnt;
    }
};

struct Tarjan:Graph{//双联通分量, 割边, 桥, 边双联通缩点
    struct Bridge{int u,v;}bridge[maxn];
    int dfn[maxn],low[maxn],belong[maxn],vis[maxn],sta[maxn],sta_,nums,bridge_;
    void ini(int n){
        for(int i=0;i<=n;i++) vis[i]=0;
        bridge_=0;
        nums=0;
        Graph::ini(n);
    }
    void tarjan(int u,int father,int&step){
        low[u]=dfn[u]=++step;
        sta[++sta_]=u;
        vis[u]=1;
        bool firsttimes=true;//用于判重边
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&firsttimes) {
                firsttimes=false;
                continue;
            }//父边
            if(vis[v]==1) low[u]=min(low[u],dfn[v]);//回边,终点在栈中
            else {//树边
                tarjan(v,u,step);
                low[u]=min(low[u],low[v]);
                if(low[v]>dfn[u]) bridge[++bridge_]=Bridge{u,v};
            }
        }
        if(low[u]==dfn[u]){
            while(sta[sta_]!=u) belong[sta[sta_--]]=nums+1;
            belong[sta[sta_--]]=++nums;
        }
    }
}graph;