RNQOJ PID28 / [Stupid]愚蠢的宠物

勉勉强强够着点并查集的边，题目吧他分类到并查集也无可厚非，这里与常规的并查集的区别在于要做一个mark数组进行一下标记，展开来说就是对于要查询的A，B,先对A进行处理，把A所有的前驱也就是双亲节点进行标记，之后再对B进行查询，一旦发现B或者离B最近的那个前驱（双亲节点）被标记的话，那么当前节点就是所求了

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int mark[1000000+6];
int pre[1000000+6];
int main()
{
  int n;

  while(cin>>n)
  {
      memset(mark,0,sizeof(mark));
      int a,b;
      for(int i=0;i<=n;i++)
      {
          pre[i]=i;
      }
      for(int i=0;i<n-1;i++)
      {
          cin>>a>>b;
          pre[b]=a;
      }
      cin>>a>>b;
      while(pre[a]!=a)
      {
          mark[a]=1;
          a=pre[a];
      }
      mark[a]=1;
      while(1)
      {
          if(mark[b])
          {
              cout<<b<<endl;
              break;
          }
          else
          {
              b=pre[b];
          }
      }
  }
    return 0;
}