Tarjanアルゴリズム

いくつかの問題をした後で、Tarjanがこんなに多くの牛を使って強い計算方法を書いたことに気づきました.
現在私が学んでいるTarjanのよく使うアルゴリズムは主に二つです.
1.Tarjanアルゴリズムは接続量を求めます.
2.TarjanオフラインアルゴリズムはCLA(Cloest comon ancestor)を求めます.
一つ目が分かりやすいです.二つ目はよく分かりません.
二つの書いた比較的いいブログを紹介します.
1.http://alanyume.com/130.html
2.http://www.cnblogs.com/jackge/archive/2013/05/10/3071437.html
Tarjanオフラインアルゴリズムの中心はDFSと検索セットです.DFSを通して次の点を絶えず上に合併し、DFSの特性を利用して、find_セットの時に得た結果はちょうどCloest Common Ancestorです.
例題:
H-Cloosest Common Ancestors
Time Limit:2000 MS     メモリLimit:100000 KB     64 bit IO Format:%I 64 d&%I 64 u
Submit
Status
Practice
POJ 1470
Appint description:
 
Description
Write a program that tast as as inputa rooted tre and a list of pairs.For each pair(u,v)the program determines the closest comomon ancestor of and v the tree.The closest commmmmmmmmthe the the the stststststststststststststststststststs the aaaatotototototototototototototototototototototototototototototototototototototototototototototototototototototototototototototos theaaaaaaaacan be its own ancestor(for example in Figure 1 the ancestors of node 2 are 2 and 5)
Input
The data set、which is read from a the std input、starts with the tree description、in the form:
nrcuoff.
vertex:(nrccessors)success 1 success or 2…succeorn
…
where vertices are represented as integers from 1 to n(n==900).The tree description is followed by a list of pairs of vertices,in the form:
nrchoff uplairs
(u v)(x y)…
The input file contensts several data sets.
Note that white-spaces(tabs,spaces and line breaks)can be used freely in the input.
Output
For each common ancestor the program prints the ancestor and the number of pair for which it is an ancestor.The reults are printesd on the standout on separate lines,in the ascender of the verticenter,the the the the the the the the the the the the the the the the the mecentincenter.
For example,for the follwing tree:
Sample Input

5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1 5) (1 4) (4 2)
      (2 3)
(1 3) (4 3)

Sample Output

2:1
5:5

ベント
Huge input、scanf is recommend.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int maxN = 1100;
int n, m;
int fa[maxN], head[maxN], vis[maxN], ans[maxN];
vector<int> edge[maxN];
int query[maxN][maxN];

void init(){
    memset(fa, 0, sizeof(fa));
    memset(head, 0, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    memset(query, 0, sizeof(query));
    for(int i=0 ; i<n; ++i) edge[i].clear();
}

int find_set(int u){
    if(u == fa[u])  return fa[u];
    return fa[u] = find_set(fa[u]);
}

void LCA(int u){
    fa[u] = u;
    for(int i=0 ; i<edge[u].size(); ++i){
        LCA(edge[u][i]);
        fa[edge[u][i]] = u;
    }
    vis[u] = 1;
    for(int i=1 ; i<=n;++i){
        if(query[u][i] && vis[i]){
            ans[find_set(i)] += query[u][i];
        }
    }
}


int main(){
    while(scanf("%d", &n)!=EOF){
        init();
        for(int i=1 ; i<=n; ++i){
            int a, b;
            scanf("%d:(%d)", &a, &b); //      
            for(int j=0 ; j<b ; ++j){
                int f;
                scanf(" %d", &f);
                head[f] = 1;
                edge[a].push_back(f);
            }
        }
        scanf(" %d", &m);
        for(int i=0 ; i<m; ++i){
            int a, b;
            scanf(" (%d %d)", &a, &b);//      
            query[a][b]++;
            query[b][a]++;
        }
        int start = 0;
        for(int i=1 ; i<=n; ++i){
            if(head[i]!= 1) start = i;
        }
        LCA(start);
        for(int i=1 ; i<=n; ++i){
            if(ans[i])  printf("%d:%d
", i, ans[i]);
        }
    }
    return 0;
}