LCA 离线tarjan算法

tarjan算法是离线算法，它必须先将所有的要查询的点对存起来，然后在搜的时候输出结果。

tarjan算法很经典，因为算法的思想很巧妙，利用了并查集思想，在dfs下，将查询一步一步的搜出来。

伪代码如下：

可以看到，对于我们已经保存好的查询，假设为(u,v)，u为此时已经搜完的子树的根节点，v的位置就只有两种可能，一种是在u的子树内，另一种就是在其之外。

对于在u的子树内的话，最近公共祖先肯定是可以直接得出为u；

对于在u的子树之外的v，我们已经将v搜过了，且已经知道了v的祖先，那么我们可以根据dfs的思想，v肯定是和u在一颗子树下的，而且这颗子树是使得他们能在一颗子树下面深度最深的。而这个子树的根节点刚好就是v的并查集所保存的祖先。所以对于这种情况的(u,v)，它们的最近公共祖先就是v的并查集祖先。

poj 1470 

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

#define  MAXN 1001

int fa[MAXN];
int ques[MAXN][MAXN];
int ind[MAXN];
bool vis[MAXN];
int cnt[MAXN];
vector<int>edge[MAXN];
int n,m;

int find_father(int k) {
    if(fa[k] == k)return k;
    else return fa[k] = find_father(fa[k]);
}

void tarjan(int x){
    for (int i=1; i<=n; i++) {
        if (vis[i] && ques[x][i])
            cnt[find_father(i)] += ques[x][i];
    }
    fa[x] = x;
    vis[x] = true;
    for (int i=0; i<edge[x].size(); i++) {
        tarjan(edge[x][i]);
        fa[edge[x][i]] = x;
    }


}


int main() {
    while (~scanf("%d", &n)) {
        for (int i=1; i<=n; i++) {
            edge[i].clear();
        }
        memset(ques, 0, sizeof(ques));
        memset(vis, false, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        memset(ind, 0, sizeof(ind));

        int a, b;
        for (int i=0; i<n; i++) {
            scanf("%d:(%d)", &a, &m);
            for (int j=0; j<m; j++) {
                scanf(" %d", &b);
                edge[a].push_back(b);
                ind[b]++;
            }
        }
        scanf("%d", &m);
        for (int i=0; i<m; i++) {
            scanf(" (%d %d)", &a, &b);
            ques[a][b]++;
            ques[b][a]++;
        }

        for (int i=1; i<=n; i++)
            if (!ind[i]) {
                tarjan(i); break;
            }
        for (int i=1; i<=n; i++)
            if (cnt[i]) printf("%d:%d\n", i, cnt[i]);
    }
    return 0;
}