学步园

题意：输入A的时候 判断后面两个数的关系，输入D的时候后面两个数代表不在一个团伙。。。这题，按着食物链那个题瞎弄的，神奇的AC了，太爽了。。。

思路：并查集，给出D的时候就合并，但同时要更新关系。relation  0 1 代表 在同一伙和不在同一伙

#include<iostream>
using namespace std;
struct node
{
  int parent;
  int relation;
}e[100100];
int N,M;
void make_set()
{
  for(int i=0;i<=N;i++)
  {
    e[i].parent=i;
    e[i].relation=0;
  }
}
int find_set(int x)
{
  if(x==e[x].parent)  return x;
  else 
  {
    int t=e[x].parent;//记录原始的父亲节点
    e[x].parent=find_set(t);
    e[x].relation=(e[x].relation+e[t].relation)%2;//枚举找规律也可以，但是貌似关系情况只有0 或 1 所以%2  就可以，因为1 1 两个不同相当于  一伙0
  }
  return e[x].parent;
}
void join(int x,int y,int d)
{
  int r1,r2;
  r1=find_set(x);
  r2=find_set(y);
  e[r1].parent=r2;
  e[r1].relation=(2+e[y].relation-e[x].relation+d)%2;//向量图。。。神奇。。。
}
int main()
{
  int T;
  scanf("%d",&T);
  char c[2];
  int a,b;
  while(T--)
  {
    scanf("%d%d",&N,&M);
    make_set();
    while(M--)
    {
      //getchar();
      scanf("%s%d%d",c,&a,&b);
      if(c[0]=='A')
      {
        int r1=find_set(a);
        int r2=find_set(b);
        if(r1==r2&&e[a].relation!=e[b].relation)//相同或者不同，肯定都在一个集合，只需要判断和代表元的关系.
        {
          printf("In different gangs.\n");
        }
        else if(r1==r2&&e[a].relation==e[b].relation)
        {
          printf("In the same gang.\n");
        }
        else
        printf("Not sure yet.\n");
      }
      else
      join(a,b,1);//1代表合并的时候属于不同的团伙
    }
  }
}