搜索（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的祖先，我们只要判断一下时间戳区间的包含关系即可确定答案