Loading...

树的dfs序

check评论:0 条 remove_red_eye浏览量:302 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-13

一、DFS 序有三种,我们姑且用序列的长度来对它们进行分类:

  • n 个点,这是最简单、最常用的一种
  • 2n个点,这个用得不多,但还是有些有用的性质
  • 2n−1 个点,这个主要是用于 O(1) 求 lca

n 个点

#define N 100010
int in[N],out[N],seq[N],idc;
void dfs(int u,int f) 
{
    seq[++idc]=u;
    in[u]=idc;
    for(int t =head[u];t;t=last[t])
    {
        int v=dest[t];
        if(v==f) 
        {
            continue;
        }
        dfs(v,u);
    }
    out[u]=idc;
}

这种DFS序满足每个节点和 DFS 序中的位置一一对应,即 u 所在位置是in[u],位置i对应节点是seq[i]。每棵子树在DFS序中是连续的,即u节点代表的子树的所有节点都在[in[u],out[u]]中。有了上面的两个性质,子树修改就是DFS序上的区间修改,子树询问就是DFS序上的区间询问,从而可以用树状数组或线段树解决前三个问题。

2n 个点

这个又称树对应的一个括号序列。与上面不同的是,我们不光进来的时候将点加到序列中,出去的时候也加一次。
如果我们把进来的时候那次改成左括号,出去的那次看成右括号,那么我们得到的就是一个层层嵌套的括号序列。
[1,in[u]]中那些没有被其有括号匹配的左括号都是从根节点到u的点对应的左括号。[in[u]+1,in[v]]中那些匹配剩下的括号个数就是u到v的节点数。

2n-1 个点

DFS的过程实际上也是一个遍历边的过程,我们把边顺次接起来,那么那些串起来的节点按照顺序排列起来就是这种DFS序,有2m+1=2n−1个节点。
如果我们用in[u]表示序列中u节点第一次出现的位置,那么[in[u],in[v]]中深度最小的节点就是u和v的最近公共祖先。

chevron_left SCOI2005 互不侵犯
并查集 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名