Tarjan求LCA总结

Tarjan算法
向上标记法：
从x向上走到根节点，并标记所有经过的点
从y向上走到根节点，当第一次遇到已标记的节点时，就找到了LCA(x, y)
对于每个询问，向上标记法的时间复杂度最坏为O(n)

在深度遍历的任意时刻，我们将树中的节点分成三类：
1.我们已经访问了，但是我们还没有回溯的节点标记为1
2.我们访问过并且已经回溯到的，标记为2
3.没有访问过的节点
对于正在访问的节点x，他的父节点是标记为1的。若y是已经访问并且回溯的节点，则LCA(x, y)就是由y向上走，遇到的第一个标记为1的节点。
我们很容易想到可以使用并查集优化。
当一个节点标记为2时，我们把它合并到他父亲所在的集合（此时他的父亲一定标记为1且单独构成一个集合）
这就相当于每个完成回溯的几点都有一个指向它的父节点的指针，只需查询y所在集合的代表元素（并查集的get操作），就等价于从y向上一直走到一个开始递归但未回溯的节点，即LCA(x, y)
其实整个过程，自己在演草纸上画一遍就好了（建议换一篇博客看看）

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 struct shiki {

     int y, net;

 }e[maxn << ];

 struct enkidu {

     int self, id, nex;

 }ask[maxn << ];

 int n, m, s;

 int lin[maxn], len = ;

 int both[maxn], tot = ;

 int fa[maxn], lca[maxn];

 int vis[maxn];

 inline int read() {

     int x = , y = ;

     char ch = getchar();

     while(!isdigit(ch)) {

         if(ch == '-') y = -;

         ch = getchar();

     }

     while(isdigit(ch)) {

         x = (x << ) + (x << ) + ch - '';

         ch = getchar();

     }

     return x * y;

 }

 inline void insert(int xx, int yy) {

     e[++len].y = yy;

     e[len].net = lin[xx];

     lin[xx] = len;

 }

 inline void add(int xx, int yy, int i) {

     ask[++tot].self = yy;

     ask[tot].id = i;

     ask[tot].nex = both[xx];

     both[xx] = tot;

 }

 int getfather(int x) {

     if(x == fa[x]) return x;

     return fa[x] = getfather(fa[x]);

 }

 void LCA_tarjan(int x) {

     vis[x] = ;

     for(int i = lin[x]; i; i = e[i].net) {

         int to = e[i].y;

         if(vis[to]) continue;

         LCA_tarjan(to);

         fa[to] = x;

     }

     for(int i = both[x]; i; i = ask[i].nex) {

         int to = ask[i].self;

         if(vis[to] == )

             lca[ask[i].id] = getfather(to);

     }

     vis[x] = ;

 }

 int main() {

     memset(vis, , sizeof(vis));

     n = read(), m = read(), s = read();

     for(int i = ; i < n; ++i) {

         int x, y;

         x = read(), y = read();

         insert(x, y);

         insert(y, x);

     }

     for(int i = ; i <= n; ++i) fa[i] = i;

     for(int i = ; i <= m; ++i) {

         int x, y;

         x = read(), y = read();

         add(x, y, i);

         add(y, x, i);

     }

     LCA_tarjan(s);

     for(int i = ; i <= m; ++i)

         cout << lca[i] << '\n';

     return ;

 }

关于板子，它救活了

巴特西

Tarjan求LCA总结

最新文章

热门文章