这是 DFS 系列的第一篇 。
首先给出一个重要的定理。该定理来自《算法导论》。
An undirected graph may entail some ambiguity in how we classify edges, since $(u,v)$ and $(v,u)$ are really the same edge. In such a case, we classify the edge according to whichever of $(u,v)$ or $(v,u)$ the search encounters first.
Introduction to Algorithm 3ed. edition p.610
Theorem 22.10
In a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge. Proof Let (u, v) be an arbitrary edge of G, and suppose without loss of generalitythat u.d < v.d. Then the search must discover and finish v before it finishes u(while u is gray), since v is on u’s adjacency list. If the first time that the searchexplores edge (u, v), it is in the direction from u to v, then v is undiscovered(white) until that time, for otherwise the search would have explored this edgealready in the direction from v to u. Thus, (u, v) becomes a tree edge. If thesearch explores (u, v) first in the direction from v to u, then (u, v) is a back edge,since u is still gray at the time the edge is first explored.low 值大概是 Robert Tarjan 在论文 Depth-first search and linear graph algorithms SIAM J. Comput. Vol. 1, No. 2, June 1972 给出的概念。
(p.150)"..., LOWPT(v) is the smallest vertex reachable from v by traversing zero or more tree arcs followed by at most one frond."
代码如下
1 #define set0(a) memset(a, 0, sizeof(a)) 2 typedef vector vi; 3 vi G[MAX_N]; 4 int ts; //time stamp 5 int dfn[MAX_N], low[MAX_N]; 6 void dfs(int u, int f){ 7 dfn[u]=low[u]=++ts; 8 for(int i=0; i
