[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;
}

例如:

[2]树的DFS序

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

上一篇:Android (二维码)关于java.lang.UnsatisfiedLinkError的小案例


下一篇:C#中string.format的格式和用法