Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

题好水,人更水……

Posted by Ruby931031 at 2012-07-09 00:43:11 on Problem 1330
//真是杀鸡用牛刀。。
//链式前向星,并查集,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;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator