数据结构：带权并查集

在并查集的基础上，对其中的每一个元素赋有某些值。在对并查集进行路径压缩和合并操作时，这些权值具有一定属性

即可将他们与父节点的关系，变化为与所在树的根结点关系

本题是Bailian上的一道题，下文描述的a数组就是所谓的权，它记录了这个结点与父结点的关系

然后通过在find和union时进行特殊的处理，来将关系进一步延伸为每一个结点和其祖先结点的关系，它完美符合了带权并查集的定义

我们理解并查集这个数据结构的时候不要过于死板，我们要知道

并查集是用来维护关系的，而不是单纯一味去归并，归并，归并

下面给出一个问题尝试用并查集来解决：一共有两个类，然后告诉你若干组数据，每一组数据的两个元素不是一类的，然后在线判断两个元素是否是同一类

这个时候如果你只会归并就行不通的，还需要一些特殊的处理

我们需要在并查集的那个数组的基础之上，需要另一个数组来记录这种特殊的现象

int set[maxn],a[maxn];
//a表示这个节点和父节点的关系，0表示相同1表示不同

接下来我们的路径压缩加找祖宗函数也需要相应的调整，要不断更新a的值才行

int find(int x)
{
    if (x==set[x]) return x;
    //x的父节点是祖先节点的情况，不需要改变a的值 
    int t=find(set[x]);
    a[x]=(a[set[x]]+a[x])%2;
    //判断归并之后x和祖先的团伙关系 
    return set[x]=t;
}

归并的时候还是很简单的，但是也要同时去更新a的值

void Union(int x, int y)
{
    int fx=find(x);
    int fy=find(y);
    set[fx]=fy;
    //根据x和y不同确定x和x的祖先节点的同伙关系 
    if (a[y]==0)
        a[fx]=1-a[x];
    else
        a[fx]=a[x];
}

我们在判断的时候，已知的情况都已经归并到一棵树里面，并且有a数组记录已知情况下所有元素的关系，直接判断即可

fx=find(x);
                fy=find(y);
                if (fx!=fy)
                    printf("Not sure yet.
");
                else if(a[x]==a[y])
                    printf("In the same gang.
");
                else
                    printf("In different gangs.
");

接下来我们给出完整的实现，这道题的大意是这样的，有两个犯罪团伙，然后告诉你若干个关系，关系是两个犯人不是一个团伙的，然后在线判断给定的两个犯人之间的关系

 1 //一共有两类，给定某两个元素之间的不同类关系
 2 //判断当前给定情况下某两个元素是否同类 
 3 #include<iostream>
 4 #include <cstdio>
 5 #include <cstring>
 6 using namespace std;
 7 const int maxn=100005;
 8 int t,n,m;
 9 int fx,fy,x,y;
10 char c;
11 int set[maxn],a[maxn];
12 //a表示这个节点和父节点的关系，0表示相同1表示不同 
13 int find(int x)
14 {
15     if (x==set[x]) return x;
16     //x的父节点是祖先节点的情况，不需要改变a的值 
17     int t=find(set[x]);
18     a[x]=(a[set[x]]+a[x])%2;
19     //判断归并之后x和祖先的团伙关系 
20     return set[x]=t;
21 }
22 void Union(int x, int y)
23 {
24     int fx=find(x);
25     int fy=find(y);
26     set[fx]=fy;
27     //根据x和y不同确定x和x的祖先节点的同伙关系 
28     if (a[y]==0)
29         a[fx]=1-a[x];
30     else
31         a[fx]=a[x];
32 }
33 int main()
34 {
35 
36     cin>>t;
37     while (t--)
38     {
39         cin>>n>>m;
40         for (int i=1; i<=n; i++)
41         {
42             set[i] = i;
43             a[i] = 0;
44         }
45         while(m--)
46         {
47             cin>>c>>x>>y;
48             if (c=='A')
49             {
50                 fx=find(x);
51                 fy=find(y);
52                 if (fx!=fy)
53                     printf("Not sure yet.
");
54                 else if(a[x]==a[y])
55                     printf("In the same gang.
");
56                 else
57                     printf("In different gangs.
");
58             }
59             else
60                 Union(x, y);
61         }
62     }
63     return 0;
64 }