『算法-ACM 竞赛-图论』——Tarjan 初步 DFS 序+时间戳+欧拉序

图论——Tarjan 初步 DFS 序+时间戳+欧拉序

一、什么是 DFS 序：

DFS 序是按照先序遍历，先遍历根节点然后依次遍历左子树，右子树的过程，每次遇到新的节点就把新访问节点加到序列中，代码如下：

int DFSrk[100000];
int cnt=0;
int dfs(int u,int fa)
{
    DFSrk[cnt++]=u;
    for(int i=head[u];i;i=ege[i].next)
    {
        if(ege[i].to!=fa)dfs(ege[i].to,u);
    }
}
//vector储存 如下
int dfs(int u,int fa)
{
    DFSrk[cnt++]=u;
    for(int i=0;i<ege[u];i++)
    {
        if(ege[u][i]=fa)dfs(ege[u][i],u);
    }
}

二、DFS 序性质

我么会发现对于图中的三棵子树他们的 DFS 序连续：

A-B-C-D-E-F-G-H

B-C-D-E

F-G-H

也就是说在一棵子树上的 DFS 序，他们一定是连续的，那么我们可以做树上的差分，这里可以保留一下，稍后填坑。

一、什么是时间戳：

时间戳我们有两个标记第一个是第一次访问的时候记录一下，然后是在最后一次访问时再标记一下。

二、时间戳的性质：

我们可以直接通过时间戳来判断一个节点是否是另一个节点的子节点。

一、什么是欧拉序：

欧拉是每次访问一个点到一个点，就要存一次，无论这个点之前访问过没有，就要遇见点就存。还有就是有的会认为叶节点也访问了两次则有如下欧拉序：A-B-C-C-B-D-E-E-D-B-A-F-G-G-F-A

主要用途是 tarjan，用起来很舒服，比如求 LCA，求 LCA 以上都可以使用其实。