搜索（2）

上一节我们以图的遍历为例讲了深度优先搜索算法和实现程序。上一节中的深度优先算法可以算是基本款，很多深度优先搜索的题目就是在这个基本款的程序上进行修改

DFS展开目录

加强版 DFS 首先增加或者说变化的一点是顶点颜色。我们在基本款代码里使用 visited 数组来区分顶点，也就是 visited [x]=true 表示 x 顶点已经访问过，visited [x]=false 表示还没访问过 x 顶点。加强版中使用” 颜色” 来区分顶点

一开始所有顶点都是白色的，白色代表顶点还没有被访问过。当我们第一次遍历到一个顶点 x 时，会把顶点 x 染成灰色。灰色代表该顶点 x 已经被访问过（调用过 DFS (x)），但是还没有访问结束（DFS (x) 退出回溯），当前正在遍历的顶点还是经过 x 到达的

如果顶点 x 的所有相连的顶点都访问过了，马上要退出 DFS (x) 向上一层回溯。我们会将 x 的颜色染成黑色。黑色代表这个顶点的遍历已经结束，之后我们再也不会访问这个顶点。上面这个图就是我们已经遍历了 1->2->3->4，并且在 4 号顶点发现无路可走，回溯到 3 号顶点时的状态。123 是灰色，4 是黑色，56 是白色

除了用三种颜色区分顶点的状态，算法导论加强版还给 “开始遍历一个顶点” 事件和” 结束遍历一个顶点 “事件都打上了一个时间戳。所谓时间戳就是一个自增的整数，比如从 1 开始遍历的时间戳是 1。然后 1->2 开始遍历 2 号节点，时间戳就是 2。如果 2 再往后找不到新的顶点，那么 2 就要回溯，在回溯前会被标记为时间戳 = 3……
上面这个图描述的是，我们已经遍历了 1->2->3->4，并且在 4 号顶点发现无路可走，回溯到 3 号顶点时的状态。注意顶点里的数字是时间戳，斜杠左边是开始时间戳，右边是结束时间戳；顶点编号被省略了。灰色顶点 123 有开始的时间戳，分别是 123；黑色 4 号顶点开始 / 结束时间戳都有，是 4/5。白色顶点 56 由于还没有被遍历到，所以没有时间戳

直到整个图遍历结束，每个访问到的顶点都会被打上了两个时间戳。一个是 DFS (x) 开始的时候，时间戳是 D (x)；另一个是 DFS (x) 要结束前，时间戳是 F (x)

下面以上图为例，我们看一下有颜色标记和时间戳的加强版 DFS 的过程：
红色的边表示沿着这条边到达了一个白色的顶点，也就是还未遍历到的新顶点。虚线边表示沿着这条边到达了一个灰色节点。黑色边表示当前顶点已经遍历结束，沿着之前的红色边回溯到上一个顶点

图中这个 DFS 的时间戳是很有意思的，有的地方叫做 DFS 序号。如果我们把每个顶点的时间戳看成区间，左端点是 D (x)，右端点是 F (x)，那么这些区间会有像括号一样的嵌套关系，如下图：
我们可以看出来任意两个顶点的区间只可能有 2 种关系：(1) 两个区间相离；(2) 一个区间包含另一个区间。换句话说，不会出现像 [1, 10], [4, 13] 这样两个区间互相跨立的情况。这种关系可以形象的看成是一个匹配合法的括号序列

例 1 蓝桥杯 —— 版本分支展开目录

题目大意就是给定一个包含 N 个顶点的树，顶点编号 1~N，其中 1 是根节点。然后有 Q 个询问，每次询问 x 是不是 y 的祖先节点，是输出 YES 不是输出 NO。特别的，根据样例里询问 x=1，y=1 时输出 YES，我们知道自己也算自己的祖先

思路 1 暴力展开目录

这道题一个最直观暴力的做法就是对于每一个询问，从 y 一直向上找父节点，如果遇到 x 那么就输出 YES；如果一直找到根节点也就是 1 号节点还没遇到 x，那么就输出 NO。伪代码如下：

Query(x,y)
{
    while y != x AND y !=1
        y = y.parent
    return x == y
}

这个算法对于每一个询问的时间复杂度是 O (N) 的，所以总的时间复杂度是 O (NQ) 的，大约可以通过 30% 的数据。想拿到满分，一种做法就是利用刚才我们讲到的 DFS 时间戳区间

思路 2 DFS 时间戳展开目录

我们从 1 号节点开始 DFS，同时求出每个节点的时间戳 D (x) 和 F (x)。例如对于样例，我们可以得到如下图所示的结果：

也就是 1~6 号节点对应的区间依次是 [1, 12], [2, 5], [6, 11], [7, 8], [3, 4], [9, 10]。根据我们之前的结论：区间只可能有相离和包含两种关系，我们可以发现 x 是 y 的祖先版本当且仅当 x 的区间包含 y 的区间

例如在上图中 [2, 5] 包含 [3, 4]; [6, 11] 包含 [7, 8] 和 [9, 10]; 根节点 [1, 12] 包含所有

在我们经过 DFS 得到时间戳 D (x) 和 F (x) 之后，再利用时间戳判断 x 是不是 y 的祖先节点就非常简单了：

Query(x,y)
{
    return D(x) <= D(y) AND F(y) <= F(x)
}

只需判断 D (x) D (y) F (x) F (y) 的大小关系，时间复杂度是 O (1) 的。所以 Q 个询问的时间复杂度是 O (Q) 的。再加上 DFS 的时间复杂度 O (N) （因为是树所以边数也是 O (N) 的），算法总体的时间复复杂度是 O (N+Q) 的。很明显比之前的 O (NQ) 快很多

下面我们来看一下这道题目的完整代码：

#include<iostream>
#include <vector>
using namespace std;
int n,q,ts = 0;
vector<int> g[100001];
int d[100001],f[100001];
void dfs(int x)
{
    ts++;
    d[x] = ts;
    for(int i = 0;i < g[x].size();i++)
    {
        int y = g[x][i];
        dfs(y);
    }
    ts++;
    f[x] = ts;
    return;
}
int main() 
{
    cin >> n >> q;
    for(int i = 2;i <= n;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
    } 
    dfs(1);
    while(q--)
    {
        int x,y;
        cin >> x >> y;
        if(d[x] <= d[y] && f[y] <= f[x])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

第 21~27 行是在读入树的边。注意这里我们虽然还是用数组套 vector 的 g 来保存边。但是这个 g 和上一节我们讲的邻接表有些不一样。这道题由于是有根树，我们知道谁是谁的父节点，所以我们 g [x] 保存的是 x 的所有子节点。与邻接表相比，g [x] 没有保存 x 的父节点

第 7~18 行是 DFS 函数，参数 x 是当前访问的节点编号。Ts 是一个全局变量，表示全局的时间戳，初始值是 0。在第 8 行刚一进入 DFS (x) 函数，也就是开始访问 x 节点时，ts 要累加 1；以及在 16 行遍历完 x 的所有邻居节点，要退出 DFS (x)，结束对 x 的遍历时，ts 也要累加 1

第 10 行是我们把当前的时间戳 ts 的值赋给 d [x]，也就是计算 x 的开始时间戳。第 11~15 行是在处理所有 x 的子节点 i，递归调用 DFS (i) 进行遍历。注意给定的图是一棵有根树，并且 g [x] 保存的是 x 的子节点。所以我们在这里可以确定 i 还没有被遍历过，不需要用 visited 数组来辅助判断

最后在第 17 行，要退出 dfs (x) 之前，我们计算 x 的结束时间戳，也是当前的 ts 的值。第 29 行执行完以后，我们就完成了对这棵树的深度优先搜索，每个节点的开始时间戳和结束时间戳也都求出来了。第 31~38 行就是在处理每一个询问，对于询问 x 是不是 y 的祖先，我们只要判断一下时间戳区间的包含关系即可确定答案