POJ 1470 Closest Common Ancestors
Wiki 上的 Tarjan 算法, Tarjan is an offline algorithm
http://en.wikipedia.org/wiki/Tarjan's_off-line_lowest_common_ancestors_algorithm
function TarjanOLCA(u)
MakeSet(u);
u.ancestor := u;
for each v in u.children do
TarjanOLCA(v);
Union(u,v);
Find(u).ancestor := u;
u.colour := black;
for each v such that {u,v} in P do
if v.colour == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + "."
然而我實作的與上面的稍微有些不同
function TarjanOLCA(u, ancestor)
MakeSet(u);
u.ancestor := u;
u.colour := black;
for each v such that {u,v} in P do
if v.colour == black
print "Tarjan's Lowest Common Ancestor of " + u +
" and " + v + " is " + Find(v).ancestor + "."
for each v in u.children do
TarjanOLCA(v, u);
Find(u).ancestor := u;
Code for this problem:
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
//Closet common ancestors
//tarjan algorithm
const int N = 1000;
vector<int> edges[N], query[N];
int times[N];
int fa[N];
int find(int v) {
return v == fa[v]? v : fa[v] = find(fa[v]);
}
void tarjan(int v, int f) {
//cout<<"int tarjan:"<<v<<' '<<f<<endl;
fa[v] = v;
for (int i = 0; i < query[v].size(); ++i) {
int u = query[v][i];
if (fa[u] != -1) {
//u, v's closet common ancestor is find(u)
//cout<<u<<' '<<v<<" closet common ancestors is "<<find(u)<<endl;
times[find(u)]++;
}
}
for (int i = 0; i < edges[v].size(); ++i) {
int u = edges[v][i];
if (u == f) continue;
tarjan(u, v);
}
fa[v] = f;
}
int main()
{
int n, q, a, b, c;
while (scanf("%d", &n) != EOF) {
memset(fa, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= n; ++i) {
edges[i].clear();
query[i].clear();
}
//cout<<"start reading edge"<<endl;
for (int i = 1; i <= n; ++i) {
scanf("%d:(%d)", &a, &b);
while (b--) {
scanf("%d", &c);
//cout<<a<<' '<<c<<endl;
edges[a].push_back(c);
fa[c]++;
}
}
int r = -1;
for (int i = 1; i <= n; ++i) {
if (fa[i] == 0)
r = i;
}
scanf("%d", &q);
//cout<<"start reading query"<<endl;
for (int i = 0; i < q; ++i) {
scanf(" ( %d %d ) ", &a, &b);
//cout<<a<<' '<<b<<endl;
query[a].push_back(b);
query[b].push_back(a);
}
memset(times, 0, sizeof(int) * (n + 1));
memset(fa, -1, sizeof(int) * (n + 1));
tarjan(r, r);
for (int i = 1; i <= n; ++i) {
if (times[i])
printf("%d:%d\n", i, times[i]);
}
}
return 0;
}