//真是杀鸡用牛刀。。
//链式前向星,并查集,Tarjan_Offline_LCA
//以后试着写写RMQ的
//32ms
#include <stdio.h>
#include <string.h>
#define MAXN 10010
struct Edge{
	int to;
	int next;
};

Edge edge[MAXN+10];
int head[MAXN+10],p[MAXN+10],qx,qy;
bool bFind,isroot[MAXN+10],visit[MAXN+10];

int find(int x){
	if (p[x]!=x)	p[x] = find(p[x]);
	return p[x];
}

void LCA(int u){
	p[u] = u;
	visit[u]=true;

	for (int k=head[u]; k!=-1; k=edge[k].next)
		if (!visit[edge[k].to])
		{
			LCA(edge[k].to);
			p[edge[k].to]=u;
			if (bFind)	return;
		}

	if (u==qx && visit[qy])
	{
		printf("%d\n",find(qy));
		bFind = true;
		return;
	}
	if (u==qy && visit[qx])
	{
		printf("%d\n",find(qx));
		bFind = true;
		return;
	}
}

int main()
{
	int t,n,i,s,e,rear;
	scanf("%d",&t);
	while (t--)
	{
		rear=0;
		scanf("%d",&n);
		memset(head,-1,sizeof(head));
		memset(isroot,true,sizeof(isroot));
		memset(visit,0,sizeof(visit));

		for (i=1;i<n;i++)
		{
			scanf("%d %d",&s,&e);	//链式前向星
			isroot[e] = false;
			edge[rear].to = e;
			edge[rear].next = head[s];
			head[s] = rear++;
		}
		scanf("%d %d",&qx,&qy);

		for (i=1;i<=n;i++)		//找到根节点
			if (isroot[i])	break;
		bFind = false;
		LCA(i);
	}
	return 0;
}

• Re:题好水，人更水…… (17) Ruby931031 2012-07-09 00:44:15
  • Re:题好水，人更水…… (21) dandong 2012-07-16 10:36:17