POJ-1470 Closest Common Ancestors【LCA】

题目链接:http://poj.org/problem?id=1470

解题思路:

第一次用RMQ+LCA搞了2天。http://blog.csdn.net/niushuai666/article/details/7424177

早上学了一下Targan离线求LCA。

代码如下：

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

const int N = 1010;
const int M = 1000010;

int in[N], pre[N], ans[N];
bool visit[N];
int vnum, edge, query;

struct st
{
	int top;
	int Head[N], Next[M], Key[M];

	void add(int u, int v)
	{
		Key[top] = v;
		Next[top] = Head[u];
		Head[u] = top++;
	}
	void clear(){
		top = 0;
		memset(Head, -1, sizeof(Head));
	}
	st(){
		clear();
	}
}son, que;

int Find_Set(int x)
{
	if(x != pre[x])
		pre[x] = Find_Set(pre[x]);
	return pre[x];
}

void lca(int cur)
{
	pre[cur] = cur; //初始化pre
	for(int i = son.Head[cur]; i != -1; i = son.Next[i])
	{
		lca(son.Key[i]);
		pre[son.Key[i]] = cur;
	}
	visit[cur] = true;
	for(int i = que.Head[cur]; i != -1; i = que.Next[i])
		if(visit[que.Key[i]])
			ans[Find_Set(que.Key[i])]++;
}

void init()
{
	memset(in, 0, sizeof(in));
	memset(visit, false, sizeof(visit));
	memset(ans, 0, sizeof(ans));
}

int main()
{
	int root, u, num, v;
	while(scanf("%d", &vnum) != EOF)
	{
		init();
		son.clear(), que.clear();
		for(int j = 0; j < vnum; ++j)
		{
			scanf("%d:(%d)", &u, &num);
			for(int i = 0; i < num; ++i)
			{
				scanf("%d", &v);
				son.add(u, v);
				in[v]++;
			}
		}
		for(root = 1; in[root]; ++root);
		scanf("%d", &query);
		while(query--)
		{
			scanf(" (%d %d)", &u, &v);
			if(u == v)
				que.add(v, u);
			else
			{
				que.add(u, v);
				que.add(v, u);
			}
		}
		lca(root);
		for(int i = 1; i <= vnum; ++i)
			if(ans[i])
				printf("%d:%d\n", i, ans[i]);
	}
	return 0;
}