tarjan点双联通

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],cnt,n;
    void ini(int n){
        this->n=n; cnt=-1;
        for(int i=0;i<=n;i++) head[i]=-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;
    }
}tree;

struct Tarjan:Graph{//割点
    int low[maxn],dfn[maxn],cut[maxn];
    int step;
    void tarjan(){
        step=0;
        for(int i=0;i<=n;i++) dfn[i]=cut[i]=0;
        for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快
    }
    void tarjan(int u,int father=0){//此函数不开放
        low[u]=dfn[u]=++step;
        int first=1, son=0;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&!first) first=false;
            else if(dfn[v]) low[u]=min(low[u],dfn[v]);
            else{
                son++;
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                //一个顶点u是割点,当且仅当1或2
                //1.u为树根且u有多与一个子树
                //2.u不为树根且存在边(u,v)为树边，使得dfn[u]<=low[v]
                if(father!=0&&dfn[u]<=low[v]) cut[u]=1;
                if(father==0&&son>1) cut[u]=1;
            }
        }
    }
}graph;