图论——Tarjan算法求lca

March 11, 2019

1416 views

1216 words

*   **tarjan算法本质是使用并查集对“向上标记法”的一种优化。它是一个离线算法。理论时间复杂度为$O(n+m)$。**
*   **在dfs当中，树中的节点一共可以分为3类：**
    1.  已经访问完毕并且回溯的节点。在这些节点标记2。
    2.  已经开始递归，但是尚未回溯的节点。这些节点就是当前正在访问的节点$x$以及$x$的祖先。在这些节点标记1。
    3.  尚未访问的节点。不标记。
*   对于正在访问的节点$x$，它到根节点的路径以及标记为1。若$y$是以及访问完回溯的节点，那么$lca(x,y)$就是从y节点向上走，直到遇到第一个标记为1的节点。
    
*   可以使用并查集对此进行优化，即每次回溯时，把它所在的集合合并到它父亲所在的集合当中，这样，$lca(x,y)$只需查询$get(y)$，就等价于从y向上找到第一个标记为1的节点。
*   每当dfs回溯时，扫描有关x的所有讯问，若y的标记为2，则$lca(x,y)$就是$get(y)$。

#### 代码如下：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    const int SIZE=500009;
    struct Edge{
        int to,next;
    }e[SIZE*2];
    int deep[SIZE],fa[SIZE],tot,head[SIZE],tag[SIZE],lca[SIZE];
    int n,m,s;
    vector<int> ask[SIZE],ask_id[SIZE];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].next=head[x];
        head[x]=tot;
    }
    
    int get(int x){
        return x==fa[x]?x:fa[x]=get(fa[x]);
    }
    
    void tarjan(int x){
        tag[x]=1;
        for(int i=head[x];i;i=e[i].next){
            int y=e[i].to;
            if(tag[y]) continue;
            deep[y]=deep[x]+1;
            tarjan(y);
            fa[y]=x;
        }
        for(int i=0;i<ask[x].size();i++){
            if(tag[ask[x][i]]==2){
                lca[ask_id[x][i]]=get(ask[x][i]);
            }
        }
        tag[x]=2;
    }
    
    int main(){
        cin>>n>>m>>s;
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
        }
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            ask[x].push_back(y);
            ask[y].push_back(x);
            ask_id[x].push_back(i);
            ask_id[y].push_back(i);
        }
        tarjan(s);
        for(int i=1;i<=m;i++){
            printf("%d\n",lca[i]);
        }
        return 0;
    }
```

Last modification：March 14, 2020