题目描述
背景
大家都知道，sheep有两只可爱的宠物（一只叫神牛，一只叫神菜）。有一天，sheep带着两只宠物到狗狗家时，这两只可爱的宠物竟然迷路了……
描述
狗狗的家因为常常遭到猫猫的攻击，所以不得不把家里前院的路修得非常复杂。狗狗家前院有N个连通的分叉结点，且只有N-1条路连接这N个节点，节点的编号是1-N（1为根节点）。sheep的宠物非常笨，他们只会向前走，不会退后（只向双亲节点走），sheep想知道他们最早什么时候会相遇（即步数最少）。
N的范围《=1000000
输入格式
第1行：一个正整数N，表示节点个数。
第2~N行：两个非负整数A和B，表示A是B的双亲。（保证A,B<=n）
第N+1行：两个非负整数A和B，表示两只宠物所在节点的位置。（保证A,B<=n）
输出格式
输出他们最早相遇的节点号。
样例输入
10
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
3 6
样例输出
1
解题思路：
利用并查集中的合并的思想，父节点表示法表示每一个元素。然后任选一个宠物，从该宠物所在的节点开始,搜索它的父节点，并且对搜索的路径进行标记。然后选择另一个宠物，同样从所在结点开始搜索，搜索它的父节点，如果在搜索路径中碰到了被标记的某个节点，那么该节点就是第一个相遇节点。
AC代码：
#include<iostream>
#include<string.h>
using namespace std;
int set[1000001];
int N;
bool vis[1000001];
int Find(int k)
{
if(vis[k])
returnk;
vis[k]=true;
if(k==set[k])
returnk;
returnset[k]=Find(set[k]);
}
int main()
{
cin>>N; //输入节点数
memset(vis,0,sizeof(vis));
intA,B;
for(inti=2;i<=N;++i)
{
cin>>A>>B;
set[B]=A;
}
cin>>A>>B;
Find(A);
cout<<Find(B)<<endl;
return0;
}
