dfs时间戳

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。时间戳是DFS的一种应用，用于记录节点被访问的时间顺序。通过时间戳，我们可以了解节点的访问顺序以及子树的范围。

时间戳在许多算法中都有应用，例如：

  • 树的重链剖分：在树的重链剖分中，时间戳用于标记节点的访问顺序。（目前主要是这个）
  • 拓扑排序：通过DFS时间戳可以实现拓扑排序。
  • 强连通分量：在图中找到强连通分量。

用法如下所示（记录节点的访问顺序）

1
2
3
4
5
6
7
8
9
10
11
12
// 记录当前节点对应在字符串的区间
int time = 0;
private void dfs(int cur, List<Integer> g[], char cs[], char dfsStr[], int nodes[][]) {
    nodes[cur][0] = time;
    for (int nxt : g[cur]) {
        dfs(nxt, g, cs, dfsStr, nodes);
    }
    dfsStr[time++] = cs[cur];
    nodes[cur][1] = time;
}
// 获得节点i对应的字符串左右端点
int l = nodes[i][0], r = nodes[i][1]-1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 记录当前节点在树中的区间，来判断两个节点的祖父关系
int time = 0;
int dfs(int pre, int cur, List<Integer> g[], int nums[]) {
    in[cur] = ++time;  // 写成time++调试半天，晕
    int res = nums[cur];
    for (int nxt : g[cur]) {
        if (nxt == pre) continue;
        res ^= dfs(cur, nxt, g, nums);;
    }
    out[cur] = time;
    return xor[cur] = res;
}
// 判断两个节点的祖父关系
if (in[i] < in[j] && in[j] <= out[i]) {  // i是j的祖先