求最近公共祖先.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <iostream>
#include <stdio.h>
using namespace std;

#define NMAX 10010
int zuxian[NMAX];

//求最近公共祖先
/*
输入：
1
8
1 2
2 4
1 3
3 5
3 6
6 7
6 8
5 8

输出：
3
*/
void init(int num)
{
	int i;
	for(i=1;i<=num;i++)
		zuxian[i]=0;
}

int cal(int a,int b)
{
	int aa[NMAX],bb[NMAX],i,t,numa,numb;
	i=0;
	t=a;
	while(t!=0)
	{
		aa[i]=t;
		t=zuxian[t];
		i++;
	}
	numa=i;
	i=0;
	t=b;
	while(t!=0)
	{
		bb[i]=t;
		t=zuxian[t];
		i++;
	}
	numb=i;
	for(i=0;aa[numa-i-1]==bb[numb-i-1];i++);
	return aa[numa-i];
}

int main()
{
	int shijian,num,ta,tb;
	scanf("%d",&shijian);
	for(;shijian;shijian--)
	{
		scanf("%d",&num);
		init(num);
		for(;num-1;num--)
		{
			scanf("%d%d",&ta,&tb);
			zuxian[tb]=ta;
		}
		scanf("%d%d",&ta,&tb);
		cout<<cal(ta,tb)<<endl;
	}
	return 0;
}