/*******************************
图的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;
//-----------------------------------------------------------