? ? ? ? 深度優(yōu)先搜索的利用。

---

????????在一個無向連通圖中，如果刪掉某個頂點后，圖不再連通（即任意兩點之間不能互相到達），我們稱這樣的頂點為割點。

????????在一個無向連通圖中，如果刪掉某條邊后，圖不在連通，這就是割邊。

? ? ? ? 我們來看一個例子：

重要城市

? ? ? ? 我們已經(jīng)掌握了敵人的城市地圖，為了在戰(zhàn)爭中先發(fā)制人決定向敵人的某個城市上空投放炸彈，來切斷敵人城市之間的通訊和補給，城市地圖如下。

?????????

? ? ? ? 肉眼可見，刪除二號頂點后，圖便不在連通。那么我們?nèi)绾卧O(shè)計程序來判斷呢？

? ? ? ? 最直接的方法是遍歷每一個頂點，判斷該點刪除后，其它頂點是否連通，用鄰接表存儲，時間復(fù)雜度為。

? ? ? ? 現(xiàn)在要講的Tarjan算法，在樸素算法的基礎(chǔ)上優(yōu)化，可以把時間復(fù)雜度降低到。

Tarjan算法(圖的割點)

????????Tarjan算法相較于樸素方法，我認為就是在深度搜索的時候已經(jīng)處理了哪些是割點（因為遍歷的時候肯定會遇到割點），而不需要再遍歷n個頂點去刪除所以它的時間復(fù)雜度去除了外面的變成了。

? ? ? ? 為了突出Tarjan算法部分，我們先用鄰接矩陣來寫這道題，時間復(fù)雜度為。

? ? ? ? 所以最主要的就是深度搜索部分，我們先來想一下樸素方法的深度搜索，其實就是構(gòu)成了一個生成樹（每一個無向連通圖都有生成樹）

? ? ? ? 本圖的一個生成樹如上所示，num數(shù)組來記錄每個頂點的時間戳（每個結(jié)點的右上角，表示第幾個被訪問到），如num[3]=2,表示頂點3第二個被訪問。

? ? ? ? 正如前面所說遍歷的時候肯定會遇到割點，如果生成樹上的一個子結(jié)點在圖中不經(jīng)過它的父結(jié)點就不能訪問已經(jīng)遍歷過的其它結(jié)點，那么它的父節(jié)點就肯定是割點了。（根節(jié)點沒有父節(jié)點，時間戳最小，需要另外判斷）

? ? ? ? 下面這個難題就轉(zhuǎn)變了，如果判斷子節(jié)點不經(jīng)過父節(jié)點訪問其它節(jié)點。這里我們用一個low數(shù)組來存儲一個節(jié)點在不經(jīng)過父節(jié)點的情況下能訪問到最遠結(jié)點的時間戳。?

? ? ? ? 對于某個頂點u，如果至少一個頂點v（即頂點的兒子），使得(兩個數(shù)組都是存的時間戳)，那么u點為割點。

? ? ? ? 對于本例，5號頂點的兒子只有6號結(jié)點，且low[6]的值為3，而5號頂點的時間戳為num[5]為5，low[6]<num[5],可以回到祖先，因此5號結(jié)點不是割點。 2號頂點的時間戳為num[2]為3，low[5]=3，low[5]==num[2],不可以回到祖先，因此2號結(jié)點不是割點。

? ? ? ? 完整代碼：（詳細理解深度搜索部分）

#include<stdio.h>
int n,m;/*頂點數(shù)和邊數(shù)*/
int root;/*根結(jié)點*/
int e[9][9]={0};/*鄰接矩陣*/
int num[9]={0},low[9]={0},flag[9]={0};
/*num記錄時間戳，low記錄不經(jīng)過父節(jié)點到達的最遠時間戳
flag記錄是否為割點*/int min(int a,int b)
{return a<b ? a:b;
}void dfs(int cur,int father,int index)
{int child=0;index++;num[cur]=index;low[cur]=index;for (int i = 1; i <= n; i++){if (e[cur][i]==1){if (num[i]==0)/*i頂點沒有杯訪問過*/{child++;/*子結(jié)點+1*/dfs(i,cur,index);/*繼續(xù)往下遍歷*/low[cur]=min(low[cur],low[i]);/*包含通過子節(jié)點訪問的最早時間戳*/if (cur!=root && low[i]>= num[cur])/*當前結(jié)點不為根結(jié)點，子節(jié)點不能不通過父節(jié)點訪問到之前的結(jié)點，該點為割點*//*不能為根結(jié)點是因為low[i]最小為root*/{flag[cur]=1;}else if(cur==root && child>=2)/*為根結(jié)點，且在生成樹中（不是圖），有兩個兒子*//*生成樹中有兩個兒子肯定是割點，沒有兩個兒子也有可能是割點*/flag[cur]=1;}else if (i!=father)/*訪問到的不是父節(jié)點，代表可以繞過了父節(jié)點*/{low[cur]=min(low[cur],num[i]);}     }}return ;
}int main()
{int x,y;scanf("%d %d",&n,&m);for (int i = 1; i <= m; i++){scanf("%d%d",&x,&y);e[x][y]=1;e[y][x]=1;/*無向圖*/}root = 1;dfs(1,root,0);for (int i = 1; i <= n; i++){if (flag[i]==1){printf("%d ",i);}}return 0;
}

? ? ? ?

?輸入格式:

? ? ? ? 輸入m+1行，第一行兩個數(shù)n和m，n表示n個頂點，m表示m條邊。接下來的m行，每行形如“a b”，用來表示一條邊。

?輸出格式:

? ? ? ? 輸出一行，一個數(shù)表示花費的最少銀子數(shù)。

輸入樣例：

6 7

1 4

1 3

4 2

3 2

2 5

2 6

5 6

輸出樣例：

?2

圖的割邊

? ? ? ? 如下圖所示，左邊的圖沒有割邊，右邊的圖有割邊：

? ? ? ? 圖的割邊其實子需要修改上面代碼中的一個部分將改為，即到達的頂點不包括其父結(jié)點和已經(jīng)遍歷的時間戳小于父結(jié)點的結(jié)點，這就證明該子節(jié)點與父節(jié)點相連的邊為割邊。

? ? ? ? 由于割邊不需要額外判斷是否為根節(jié)點，故判斷那一部分可以刪除。

? ? ? ? 完整代碼（注意輸出部分）：

#include<stdio.h>
int n,m;/*頂點數(shù)和邊數(shù)*/
int root;/*根結(jié)點*/
int e[9][9]={0};/*鄰接矩陣*/
int num[9]={0},low[9]={0};
/*num記錄時間戳，low記錄不經(jīng)過父節(jié)點到達的最遠時間戳*/int min(int a,int b)
{return a<b ? a:b;
}void dfs(int cur,int father,int index)
{index++;num[cur]=index;low[cur]=index;for (int i = 1; i <= n; i++){if (e[cur][i]==1){if (num[i]==0)/*i頂點沒有杯訪問過*/{dfs(i,cur,index);/*繼續(xù)往下遍歷*/low[cur]=min(low[cur],low[i]);/*包含通過子節(jié)點訪問的最早時間戳*/if (low[i] > num[cur]){printf("%d-%d\n",cur,i);}}else if (i != father)/*訪問到的不是父節(jié)點，代表可以繞過了父節(jié)點*/{low[cur]=min(low[cur],num[i]);}     }}return ;
}int main()
{int x,y;scanf("%d %d",&n,&m);for (int i = 1; i <= m; i++){scanf("%d%d",&x,&y);e[x][y]=1;e[y][x]=1;/*無向圖*/}root = 1;dfs(1,root,0);    return 0;
}

輸入格式:

? ? ? ? 輸入m+1行，第一行兩個數(shù)n和m，n表示n個頂點，m表示m條邊。接下來的m行，每行形如“a b”，用來表示一條邊。

?輸出格式:

? ? ? ? 輸出一行，一個數(shù)表示花費的最少銀子數(shù)。

輸入樣例：

6 6

1 4

1 3

4 2

3 2

2 5

5 6

輸出樣例：

5-6

2-5

參考文獻：?

《啊哈！算法》