0x21 树与图的遍历

树与图的深度优先遍历

深度优先遍历，就是在每个点\(x\)上面的的多条分支时，任意选择一条边走下去，执行递归，直到回溯到点x后再走其他的边

int head[N];
bool v[N];
struct edge
{
    int v , next;
}e[N];

inline void dfs( int x )
{
    v[x] = 1;
    for( register int i = head[x] ; i ; i = e[i].next)
    {
        register int y = e[i].next;
        if( v[y] ) continue;
        dfs( y ) ;
    }
    return ;
}

树的DFS序

一般来说，我们在对树的进行深度优先时，对于每个节点，在刚进入递归时和回溯前各记录一次该点的编号，最后会产生一个长度为\(2N\)的序列，就成为该树的\(DFS\)序

\(DFS\)序的特点时：每个节点的\(x\)的编号在序列中恰好出现两次。设这两次出现的位置时\(L[x]\),\(R[x]\)，那么闭区间\([L[x],R[x]]\)就是以\(x\)为根的子树的\(DFS\)序

inline void dfs( int x )
{
    a[ ++ tot ] = x; // a储存的是DFS序
    v[ x ] = 1;
    for( register int i = head[x] ; i ; i = e[i].next )
    {
        register int y = e[i].v;
        if( v[y] ) continue;
        dfs( y );
    }
    a[ ++ tot ] = x;
    return ;
}

0x20 搜索

原文：https://www.cnblogs.com/Mark-X/p/11519097.html