讨论 / 这题和并查集有关?
沧海一声喵 2018-02-26 23:22:36
点我顶贴 收藏 删除
#include <cstdio>

#include <cstdlib>

#include <vector>

using namespace std;

int main(){

int i,j,x,y,n,*fa;

vector<int> v1,v2;

scanf("%d",&n);

fa=(int *)malloc((n+1)*sizeof(int));

for(i=1;i<=n;i++) fa[i]=i;

for(i=1;i<n;i++){

scanf("%d%d",&x,&y);

fa[y]=x;}

scanf("%d%d",&x,&y);

while(x!=1){

v1.push_back(x);

x=fa[x];}

v1.push_back(1);

while(y!=1){

v2.push_back(y);

y=fa[y];}

v2.push_back(1);

for(i=0;i<v1.size();i++)

for(j=0;j<v2.size();j++)

if(v2[j]==v1[i]){

printf("%d",v1[i]);return 0;}}

查看更多回复
提交回复