好最近公共祖先二525lca.cpp

来自「设计一个算法」· C++ 代码 · 共 67 行

#include<iostream>
#include<fstream>
using namespace std;

int lca(int array[],int p,int q,int l);
int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!"<<endl;
		exit(1);
	}
	int *array,*b,m,count,k=0,i,j,l,result,n;
	in>>n;
	array=new int [n+1];
	for(count=1;count<=n;count++)
	{
		in>>k;
		for(k;k>0;k--)
		{
			in>>j;
			array[j]=count;
		}
	}
	array[1]=1;
	array[0]=1;
	in>>m;
	b=new int [2*m];
	for(count=0;count<m;count++)
	{
		i=2*count;
		j=2*count+1;
		in>>b[i]>>b[j];
	}
	for(count=0;count<m;count++)
	{
		i=2*count;
		j=2*count+1;
		l=b[j];
		result=lca(array,b[i],b[j],l);
		out<<b[i]<<' '<<b[j]<<' '<<result<<endl;
	}
	delete []array;
	delete []b;
	return 1;
}


int lca(int array[],int p,int q,int l)
{
	if(p==q)
		return p;
	else
	{
		if(q==1)
		{
			lca(array,array[p],l,l);
		}
		else
		{
			lca(array,p,array[q],l);
		}
	}
}