成都外国语学校信息学集训课 Day11

不知不觉间,暑假就过去了一半,我还是个垃圾。

讲讲一些DFS序列相关的问题,本质就是把树扯成一个线性的结构。

在DFS的过程中,L[u]和R[u]表示节点第一次访问到u的时间和离开u的时间,这样我们要对u的子树进行信息维护时就可以直接维护序列L[u]到R[u]这连续的一段。

代码如下:

void dfs( int u, int fa ) {
    L[u] = ++dfs_clock;
    for ( int i = head[u]; i; i = e[i].next ) {
        int v = e[i].v;
        if ( v == fa )
            continue;
        dfs( v, u );
    }
    R[u] = dfs_clock;
}
Last modification:July 24th, 2019 at 08:48 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment