邊雙聯通分量（e-DCC）的求法 & 縮點

思路：求出給出的無向圖中所有的橋，從原圖中删去橋，

得到到的所有聯通塊均為邊雙聯通分量。

是以有兩個步驟：

①tarjan求出所有割邊并标記

②dfs劃分聯通塊

#define ll long long
using namespace std;
const int SIZE=100010;
int head[SIZE];
int ver[SIZE*2];
int Next[2*SIZE];
int dfn[SIZE];
int low[SIZE];//該點兩個low值來源中最小的時間戳值
int n,m,tot,num;//邊數、時間戳
bool bridge[2*SIZE];
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;//從上往下搜尋時預處理x點的時間戳和回溯值
    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],dfn[y]);//low【x】值的兩種來源之後一種，y通過一條非樹邊到達x
    }
}
int c[SIZE];//點 所屬于的聯通塊編号
int 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);
    }
}
int main()
{
    cin>>n>>m;
    tot=0;
    num=0;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&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<tot;i+=2)
        if(bridge[i])printf("%d %d",ver[i^1],ver[i]);
        
        
    for(int i=1;i<=n;++i)
    {
        if(!c[i])//目前不屬于任何聯通塊的點
        {
            ++dcc;//聯通塊的标号
            dfs(i);
        }
    }    
    return 0;
}
           

縮點模闆（略微和書上有不同，具體正确性未測試）：

#define ll long long
using namespace std;
const int SIZE=100010;
int head[SIZE];
int ver[SIZE*2];
int Next[2*SIZE];
int dfn[SIZE];
int low[SIZE];//該點兩個low值來源中最小的時間戳值
int n,m,tot,num;//邊數、時間戳
bool bridge[2*SIZE];
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;//從上往下搜尋時預處理x點的時間戳和回溯值
    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],dfn[y]);//low【x】值的兩種來源之後一種，y通過一條非樹邊到達x
    }
}
int c[SIZE];//點 所屬于的聯通塊編号
int 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);
    }
}
int hc[SIZE];//點的首條邊，head
int vc[SIZE*2];//邊的終點ver
int nc[SIZE*2];//Next數組
int tc;//縮點後的邊數
void add_c(int x,int y)
{
    vc[++tc]=y;
    nc[tc]=hc[x];
    hc[x]=tc;
}
int main()
{
    cin>>n>>m;
    tot=1;
    num=0;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])tarjan(i,0);//搜一片森林
    for(int i=2;i<=tot;i+=2)
        if(bridge[i])printf("%d %d",ver[i^1],ver[i]);
        
        
    for(int i=1;i<=n;++i)
    {
        if(!c[i])//目前不屬于任何聯通塊的點
        {
            ++dcc;//聯通塊的标号
            dfs(i);
        }
    }    
    
    //縮點
    
    tc=1;
    for(int i=2;i<=tot;i+=2)//i+=2，有差別和書上
    {

        int x=ver[i^1],y=ver[i];
        if(c[x]==c[y])continue;
        add_c(c[x],c[y]);
        add_c(c[y],c[x]);//沒測試，具體再與書上對比一下
    }
    for(int i=2;i<=tc;i+=2)
        cout<<vc[i^1]<<" "<<vc[i]<<endl;
    return 0;
}
           

The end；