/*******************************
圖的DFS信息構建 by oyjpArt
g矩陣: g[i][j] -> 0 : 無邊
1 : 可重復訪問邊
-1: 非可重復訪問邊
說明:以為在無向圖中u->v訪問之后就不能再從v->u訪問了
故{u, v}訪問了之后{v, u}要置-1
如果是有向圖 則沒有這個規則
gc矩陣:gc[i][j]-> 0 : 無邊
1 : 樹枝邊
2 : 反向邊
3 : 正向邊
4 : 交叉邊
d數組: 頂點的開始訪問時間表
f數組: 頂點的結束訪問時間表
c數組: 頂點顏色表 0白色 -1灰色 1黑色
p數組: 頂點的前驅表
l數組: 頂點的L值(最頂層的祖先層數)
b數組: 頂點的度數表
關于標號函數 LOW()
LOW(U)代表的是與U以及U的子孫直接相連的結點的最高輩分（深度）
d[U] U首次被訪問時
LOW[U] = min(LOW[U], d[W]) 訪問邊{U,W}
min(LOW[U], LOW[S]) U的兒子S的關聯邊全部被訪問時
/*******************************/
const int maxn = 100;
int n, g[maxn][maxn], gc[maxn][maxn];
int d[maxn], f[maxn], l[maxn], p[maxn], c[maxn], b[maxn];
int time;
void dfs_visit(int u) {//遞歸搜索以U為根的深度優先樹
int v;
c[u] = -1; //置頂點為灰色//去掉這句之后適用于有向圖(后面設置不可訪問亦同)
time++; d[u] = time, l[u] = time;
for(v = 1; v<=n; v++)
if(g[u][v] > 0)
if(c[v] == 0) { //如果v是白色節點
g[v][u] = -1; //不可再訪問
gc[u][v] = 1; //樹枝邊
b[u]++; //度數
p[v] = u; //記錄父親節點
dist_visit(v); //遞歸搜索以v為根的深度優先樹
if(l[v] < l[u]) //v是u的后代
l[u] = l[v]; //u的兒子v的關聯邊搜索完后計算父親的low值
g[v][u] = 1; //恢復可訪問標志
}
else {
if(c[v] < 0) { //若頂點為灰色
if(l[v] < l[u]) //u與v相連
l[u] = l[v];
gc[u][v] = 2; //反向邊
}
else { //黑色
if(d[v] > d[u])
gc[u][v] = 3; //正向邊
else
gc[u][v] = 4; //交叉邊
}
}
c[u] = 1; //DFS完畢 置黑色吧
time++; f[u] = time;
}
void dfs() {
int u;
memset(gc, 0, sizeof(gc));
memset(c, 0, sizeof(c));
memset(b, 0, sizeof(b));
time = 0;
for(u = 1; u <= n; u++)
if(c[u] == 0) {
p[u] = 0;
dfs_visit(u);
}
}
/*******************************
DFS3大經典應用
一: TOPO排序
DFS之后按照結束訪問時間反向排序即可 如果在DFS過程中出現方向邊(成環) 則無法TOPO
當然我們還有一種經典的TOPO方法 找0度節點迭代刪除法 o(M+N)的TC
二: 求割點和橋
判定規則1: 如果root節點又多于一個1子節點 則root是割點
判定規則2: 如果一個節點u有某一個子節點v不含到u的祖先節點的后向邊 則u為割點
即對于u的子節點v, u是割點的條件 (p[u] == 0 && b[v] > 1) || (p[u] > 0 && l[v] >= d[u])
橋: 不屬于任何簡單回路的邊 "一牽動全身" l[v] > d[u]即是橋
之所以不能等于 實際上等于的情況是存在2條以上的邊 自然就不是橋了~
(注意加上割點表 以防重復輸出)
三: 求有向圖的極大強連通分支
1.對圖進行DFS遍歷 遍歷中記下所有的結束時間A[i].遍歷的結果是構建的一座森林W1
我們對W1中的每棵樹G進行步驟2到步驟3的操作
2.改變圖G中每一條邊的方向 構造出新的有向圖Gr
3.按照A[i]由小到大的順序對Gr進行DFS遍歷.遍歷的結果是構建了新的樹林W2.
W2中每棵樹上的頂點構成了有向圖的極大強連通分支
/*******************************/
//一個更加簡潔的程序框架(來自<<算法藝術與信息學競賽>>)-------
這里面的Ancestor相當于上面所說的LOW
Procedure DFS(節點編號k, k的父親節點編號father, deep:integer)
var i, tot : integer;
begin
C[k] = -1; {灰色}
D[k] = deep; {記錄深度}
Ancestor[k] = deep, tot = 0;
for i = 1->n
begin
if(節點i和k相連) and (i != father) and (Ci = -1)
then Ancestor[k] = Min(Ancestor[k], Di);
if(節點i與k相連) and (Ci = 0) then
begin
DFS(i, k, deep + 1);
tot++, Ancestor[k] = Min(Ancestor[k], Ancestor[i]);
if(k == Root) and (tot > 1) or
( (k != Root) and (Ancestor[i] >= D[k]) )
then Cut[k] = true;
if(Ancestor[i] > D[k]) then Brige[k][i] = true
end
end
C[k] = 1; //黑色
time++, A[i] = time;
end;
//-----------------------------------------------------------