并查集
先写的简单一点，之后补充

poj 1703
题目： 1703
这个并查集有三种方法
参考 csdn：Kjctar
第一种，加一个数组用来判断敌对关系，使用这个数组来判断是否敌对

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5 + 100 ;
int p[N] ;
int d[N] ; //  记录敌对关系，每次清零

int find(int x){
    if(p[x] != x) p[x] = find(p[x]) ;
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}

//这道题不可以用cin，cout
int main()
{
    int t;
    scanf("%d",&t) ;
    while(t--){
        int n, m ;
        memset(d,0,sizeof d) ;
        scanf("%d %d",&n,&m);

        for(int i = 0 ;i <= n ; i++){
            p[i] = i ;
        }

        for(int i = 0 ; i < m ; i++){
            char opt ;
            int a,b ;
            scanf("%*c%c %d %d",&opt,&a,&b) ;

            if(opt == 'A'){
                if(find(a) == find(b)){
                    cout << "In the same gang." << endl ;
                }
                else if(d[find(a)] == find(b)){ //原文这里还有一个&&d[find(a)] != 0 ,没必要find（b）！= 0  
                    cout << "In different gangs." << endl ;
                }
                else {
                    cout << "Not sure yet." << endl ;
                }
            }
            else{
                int fa = find(a) ; //找到a的帮派老大
                int fb = find(b) ;
                if(d[fa]){          //fa有敌对关系
                    marge(d[fa],b) ; // 将b与fa的敌对合并
                }
                if(d[fb]){
                    marge(d[fb],a) ;
                }
                fa = find(a) ;    //重新寻找老大
                fb = find(b) ;
                d[fa] = fb ;     //记录敌对关系
                d[fb] = fa ;
            }
        }
    }
    return 0;
}

扩展域并查集

第二种方法
将敌对关系记录，这样写如果给的每组数据都直接有效的话（就是直接推出来各自帮派），就会形成两个集合，每个集合
中分别有自己的自己的成员和敌对成员，自己成员都小于等于n
相当于扩展域的并查集

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 2e5 + 100 ;
int p[N] ;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]) ;
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}

int main()
{
    int t;
    scanf("%d",&t) ;
    while(t--){

        int n , m ;
        scanf("%d %d",&n,&m) ;

        for(int i = 0 ; i <= 2 * n ; i ++){
            p[i] = i ;
        }

        for(int i = 0 ; i < m ; i++){
            int a,b ;
            char ch ;
            scanf("%*c%c %d %d",&ch,&a,&b) ;

            if(ch == 'A'){
                if(find(a) == find(b) ){
                    cout << "In the same gang." << endl ;
                }
                else if(find(a) == find(b + n)){
                    cout << "In different gangs." << endl ;
                }
                else {
                    cout << "Not sure yet." << endl ;
                }
            }
            else{
                marge(a,b+n) ; 
                marge(a+n,b) ;
            }
        }

    }

    return 0;
}

带边权的并查集

第三种
可以看作是定义了两个帮派，使用r来记录帮派，r = 1 ，代表帮派敌对

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5 + 100 ;
int p[N] ;
int r[N] ;

int find(int x){
    if(p[x] == x) return x ;
    int item = p[x] ;
    p[x] = find(p[x]) ;
    r[x] = (r[x] + r[item]) % 2;
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    p[fa] = fb ;
    r[fa] = (r[a] + 1 + r[b]) % 2 ;  //因为在合并的时候知道a与b一定是敌对关系所以中间之间加上1了
}

int main()
{
    int t;
    scanf("%d",&t) ;

    while(t--){
        int n,m ;
        scanf("%d %d",&n,&m) ;

        memset(r,0,sizeof r) ;
        for(int i = 0 ; i <= n ; i++){
            p[i] = i ;
        }

        for(int i = 0 ; i < m ; i++){
            int a,b ;
            char ch ;
            scanf("%*c%c %d %d",&ch,&a,&b) ;
            if(ch == 'A'){
                if(find(a) != find(b)){
                    cout << "Not sure yet." << endl ;
                }
                else{
                    if(r[a] == r[b]){
                        cout << "In the same gang." << endl ;
                    }
                    else{
                        cout << "In different gangs." << endl ;
                    }
                }
            }
            else{
                marge(a,b) ;
            }
        }
    }
    return 0;
}

最后附上第三种解法的向量思维详解 csdn向量思维