无向图双连通分量与缩点相关概念

书P401

需要具备的知识：
①：tarjan求割点与割边：https://blog.nowcoder.net/n/dc5fbd4588164fb4b37847a11ea7f499

若一张无向图不存在割点，则为点双连通图。
若一张无向图不存在割边（桥），则为边双连通图。

无向图的极大点双连通子图为点双连通分量，简称“v-DCC”。
无向图的极大边双连通子图为边双连通分量，简称“e-DCC”。
二者统称为双连通分量，简称“DCC”。

1、边双连通分量
模版：https://www.luogu.com.cn/problem/T103489

#include <bits/stdc++.h>
using namespace std;
const int SIZE=3e5+1;

int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE];
bool bridge[SIZE*2];
int n,m,tot,num;

int c[SIZE],dcc;
void dfs(int x)                            
{
    c[x]=dcc;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(c[y]||bridge[i])    continue;
        dfs(y);
    }
}

void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

void tarjan(int x,int in_edge)
{
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])
            {
                bridge[i]=bridge[i^1]=true;
            }
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],low[y]);
    }
}

int main()
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])    tarjan(i,0);
    }

    for(int i=1;i<=n;i++)
    {
        if(!c[i])
        {
            ++dcc;
            dfs(i);
        }
    }
    cout<<dcc<<endl;
    //cout<<"There are "<<dcc<<" e-DCCs."<<endl;
    /*for(int i=1;i<=n;i++)
    {
        cout<<i<<" belongs to DCC "<<c[i]<<"."<<endl;
    }*/
    return 0;
}

2、

3、点双连通分量
模版题：https://www.luogu.com.cn/problem/P3225

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100010;
int head[SIZE],ver[SIZE*2],Next[SIZE*2];
int dfn[SIZE],low[SIZE],Stack[SIZE];
bool cut[SIZE*2];
vector<vector<int> > dcc;
int n,m,tot,num,root,top,cnt;
void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    Stack[++top]=x;
    if(x==root&&head[x]==0)
    {
        dcc[++cnt].push_back(x);
        return;
    }
    int flag=0;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                if(x!=root||flag>1)    cut[x]=true;
                cnt++;
                int z;
                while(z!=y)
                {
                    z=Stack[top--];
                    dcc[cnt].push_back(z);
                }
                dcc[cnt].push_back(x);
            }
        }
        else    low[x]=min(low[x],dfn[y]);
    }
}
int main()
{
    cin>>n>>m;
    tot=1;
    for(int i=0;i<=n;i++)
    {
        dcc.push_back({});
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==y)    continue;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            root=i;
            tarjan(i);
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        cout<<"v-DCC "<<i<<":";
        for(int j=0;j<dcc[i].size();j++)
        {
            cout<<" "<<dcc[i][j];
        }
        cout<<endl;
    }
    return 0;
}