做了几道题之后才发现Tarjan写了这么多牛逼的算法。
目前我所学的Tarjan经常用的算法主要就两个：
1.Tarjan算法求连通量.
2.Tarjan离线算法求CLA ( Cloest common ancestor)
第一种比较好理解，第二种就不那么好理解了。
推荐两个写的比较好的博客：
1.http://alanyume.com/130.html
2.http://www.cnblogs.com/jackge/archive/2013/05/10/3071437.html
Tarjan离线算法的核心就是 DFS 和 并查集 。通过DFS不断将下面的点不断向上合并，在利用DFS的特性，find_set(u)的时候得到的结果就刚好是Cloest Common Ancestor了。
例题：
Description
Input
Output
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
Hint
#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\n", i, ans[i]); } } return 0; }
原文：http://www.cnblogs.com/topW2W/p/5240645.html