【下海捕魚】割頂與橋的求解

Description

給出一個n個點（編号1..n），m條邊的無向圖，求圖的割頂和橋。

Input Data

包含多組測試資料，每組資料格式如下：

第一行輸入n,m（n,m <= 100000;

下面m行每行輸入u,v表示u和v之間有邊。

最後一行是n=m=0，表示資料結束。

Output Data

對于每組資料，輸出：

第一行輸出割頂的個數和橋的條數。

若割頂數不為0，則第二行開始按照節點編号從小到大輸出各個割頂，一個一行。

Input Sample

6 7

1 2

1 3

2 5

3 5

5 6

4 5

1 4

5 6

4 1

4 5

5 1

1 2

1 3

2 3

0 0

Output Sample

1 1

5

1 0

1

——————————————————分割の線——————————————————

分析

也分析不出個是以然來。因為是道模闆題，就直接介紹幾個概念，然後上代碼；

預備知識

割頂：Cut Vertex，對于無向圖G，如果删除某個頂點u後，連通分量數目增加，則u便是圖G的關節點（Articulation Vertex）或割頂。

橋：Bridge，如果删除某條邊，G就非連通了，這條邊就稱之為橋。

概念1 時間戳

某一點的時間戳即是該點在DFS中被通路的順序，如果v的時間戳小于u的時間戳則v是u的祖先 (因為祖先先通路嘛)。

用全局變量dfs_clock表示“目前時刻”，定義pre[u]表示u的順序（或稱為到達u點時的時刻）,僞代碼如下：

memset(pre,,sizeof(pre));
dfs_clock=;
pre[u]=++dfs_clock;
           

概念2 樹邊和反向邊

樹邊：在dfs森林中被周遊的邊；

反向邊：第一次處理後，子孫指向祖先的邊。可認為是除去樹邊外的所有邊。

dfs的森林

概念3 割頂特性

定理1->容易看出，割頂至少要與兩點相連，是以若為根節點，需要有兩個及以上的孩子；若不為根節點，則需要至少一個孩子結點

用low[u]表示u及其子孫所能到達的最早祖先；

定理2->容易想到的是若有一個點，它的子孫所能到達的最早的點，大于等于自己，則此點是割頂（動手畫一畫，想一想是為什麼）。用數組表示為

之後可以通過dfs求low[u]的值，順道完成求割頂和橋的操作。

代碼如下

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>g[];
int dfs_clock;
int cnt_bridge,cnt_cut;
int low[],is_cut[];
int pre[],post[];
void pre_visit(int u)
{
    pre[u]=++dfs_clock;
}
void post_visit(int u)
{
    post[u]=++dfs_clock;
}
int dfs(int u,int fa)//u在DFS數中的父親結點是fa
{
    int lowu=pre[u]=++dfs_clock;
    int child=;//子結點數目
    for(int i=;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!pre[v])//通路過v
        {
            child++;
            int lowv=dfs(v,u);
            lowu=min(lowu,lowv);//通過後代的lowv更新lowu值
            if(lowv>=pre[u]) is_cut[u]=;//如果v能到達的最早的祖先小于等于它的祖先u ，則u是割點
            if(low[v]>pre[u]) cnt_bridge++;//如果兒子v隻能到達u，則(u,v)是一座橋，删去後連通分量+1
        }
        else if(pre[v]<pre[u]&&v!=fa)//通過反向邊更新lowu的值
        {
            lowu=min(lowu,pre[v]);
        }
    }
    if(fa<&&child==) is_cut[u]=;//隻有一個子結點的根結點不是割頂
    low[u]=lowu;//更新low[u]的值；
    return lowu;//傳回值，對應父親結點的lowv
}
int main()
{
    int n,m;
    cin>>n>>m;
        memset(is_cut,,sizeof(is_cut));
        memset(pre,,sizeof(pre));
        for(int i=;i<=n;i++)
            g[i].clear();
        cnt_bridge=;
        cnt_cut=,dfs_clock=;//每次的初始化
        for(int i=;i<=m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for(int i=;i<=n;i++)
            if(!pre[i])
                dfs(i,-);
        for(int i=;i<=n;i++)
            if(is_cut[i])cnt_cut++;
        printf("%d\n",cnt_cut);
        for(int i=;i<=n;i++)
            if(is_cut[i]) printf("%d ",i);//輸出割頂
    return ;
}
           

完畢