Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 送个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: