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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

送个1Y的代码~~用邻接表存储的~~

Posted by ybc_c at 2010-12-29 00:18:58 on Problem 1330
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define M 100010
int n,m;

typedef struct node
{
	int data;
	struct node *next;
}Node,*Nodepoint;

struct tree
{
	int du;
	struct node *next;
}Tree[M];
int fa[M],level[M];

void Init()
{
	for(int i=1;i<=m;i++)
	{
		fa[i]=0;
		level[i]=0;
		Tree[i].du=0;
		Tree[i].next=NULL;
	}
}

void buidtree()
{
	Nodepoint p;
	int x,y;
	for(int i=1;i<=m-1;i++)
	{
		p=(Nodepoint)malloc(sizeof(Node));
		scanf("%d%d",&x,&y);
		fa[y]=x;
		Tree[y].du++;
		p->data=y;
		p->next=Tree[x].next;
		Tree[x].next=p;
	}
}

void LCA()
{
	int a,b,t;
	scanf("%d%d",&a,&b);
	if(level[a]<level[b])
	{t=a;a=b;b=t;}
	while(level[a]>level[b]) a=fa[a];
	while(a!=b)
	{
		a=fa[a];
		b=fa[b];
	}
	printf("%d\n",a);
}

int queue[M];
void buidlevel()
{
	Nodepoint p;
	int a,step=1;
	int front=0,rear=0,cout=0;
	for(int i=1;i<=m;i++)
		if(!Tree[i].du) {a=i;break;}
	queue[rear++]=a;
	cout++;
	level[a]=step;
	while(front<rear)
	{
		step++;
		for(int i=0;i<cout;i++)
		{
			a=queue[front++];
			p=Tree[a].next;
			while(p)
			{
				queue[rear++]=p->data;
				level[p->data]=step;
				p=p->next;
			}
		}
		cout=rear-front;
	}
}

int main()
{
	scanf("%d",&n);
	for(int p=1;p<=n;p++)
	{
		scanf("%d",&m);
		Init();
		buidtree();
		buidlevel();
		LCA();
	}
	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