[2]树的DFS序

定义：

树的DFS序就是在对树进行DFS的时候，对树的节点进行重新编号；
DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们可以解决很多问题。

代码：

void DFS(int u, int fa)

{

    L[u] = ++dfs_clock;

    for(int k = head[u]; ~k; k = E[k].next)

    {

        int v = E[k].to;

        if(v == fa) continue;

        DFS(v, u);

    }

    R[u] = dfs_clock;

}

例如：

在DFS的过程中，我们对树的每一个节点都重新编号，对于每一个节点都会产生两个数L,R，L是这个节点的新编号，R是表示从L~R的节点都是以新节点L为根的子树。

巴特西

[2]树的DFS序

定义：

最新文章

热门文章