poj 1470 关于lca离线tarjan方法的使用

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int fa[1005];
int fi(int x)
{
	if (x != fa[x])
	{
		fa[x] = fi(fa[x]);
	}
	return  fa[x];
}
struct ***//链式前向星的储存方式；
{
	int from;
	int ne;
}ed[1005];
int cnt = 0;
int head[1005];
void add(int a, int b)
{
	ed[cnt].from = b;
	ed[cnt].ne = head[a];
	head[a] = cnt++;
}
vector<int>ques[1005];用来储存问题
int ans[1005] = { 0 };//用来储存最后答案
int vis[1005] = { 0 };用来看是否之前已经遍历过
void tar(int x)
{
	for (int s = head[x]; ~s; s = ed[s].ne)
	{
	//	cout << x << endl;
		tar(ed[s].from);//继续遍历
		fa[ed[s].from] = x;//合并；
		vis[ed[s].from] = 1;//标记
		
	}
	for (int s = 0; s < ques[x].size(); s++)
	{
		if (vis[ques[x][s]])//如果之前已经遍历过，那么直接输出就好
		{
			ans[fa[fi(ques[x][s])]]++;
		}
	}
}
int in[1005];//入度
void init()
{
	memset(head, -1, sizeof(head));
	for (int s = 0; s <= 1004; s++)
	{
		fa[s] = s;
		ques[s].clear();
		ans[s] = 0;
		vis[s] = 0;
		in[s] = 0;
		ed[s].ne = -1;
	}
	cnt = 0;
}
int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		init();
		for (int s = 0; s < n; s++)
		{
			int num;
			scanf("%d", &num);
			char a;
			scanf("%c", &a);
			int su;
			scanf("%c", &a);
			scanf("%d", &su);
			scanf("%c", &a);
			for (int s = 0; s < su; s++)
			{
				int ad;
				scanf("%d", &ad);
				in[ad] = 1;
				add(num, ad);
			}
		}
		int s;
		scanf("%d", &s);
		while (s--)
		{
			char a1;
			int m, n;
			cin >> a1;
			cin >> m >> n;
			//	cout << m << n << endl;
			cin >> a1;
			ques[m].push_back(n);//双向都插入；
			ques[n].push_back(m);
		}
		for (int s = 1; s <= n; s++)
		{
			if (!in[s])//用入度这种方式找到至高点（老祖宗）；
			{
				tar(s);
				break;
			}
		}
		for (int s = 0; s < 1005; s++)
		{
			if (ans[s] != 0)
			{
				printf("%d:%d\n", s, ans[s]);
			}
		}
	}
	return 0;
}