种类并查集学习心得

快来打我* 2022-06-01 11:56 130阅读 0赞

修正信息备注：  
1.【2018-01-29】创作博文基础  
2.【2018-01-29】增加样例2.2

一、基本性质  
1.在基于并查集的基础上增加记录数组\_rank，表示i与其同集合根节点的关系

二、例题讲解  
2.1[【食物链 POJ - 1182】——vjudge题目链接][POJ - 1182_vjudge]

##### 题意： #####

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。  
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。  
有人用两种说法对这N个动物所构成的食物链关系进行描述：  
第一种说法是”1 X Y”，表示X和Y是同类。  
第二种说法是”2 X Y”，表示X吃Y。  
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。  
1） 当前的话与前面的某些真的话冲突，就是假话；  
2） 当前的话中X或Y比N大，就是假话；  
3） 当前的话表示X吃X，就是假话。  
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

##### Input: #####

第一行是两个整数N和K，以一个空格分隔。  
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。  
若D=1，则表示X和Y是同类。  
若D=2，则表示X吃Y。

##### Output: #####

只有一个整数，表示假话的数目。

##### Sample Input: #####

100 7
    1 101 1 
    2 1 2
    2 2 3 
    2 3 3 
    1 1 3 
    2 3 1 
    1 5 5

##### Sample Output: #####

题目分析：  
rank\[x\] = 0:表示x与f\[x\]为同种生物  
rank\[x\] = 1:表示x吃f\[x\]  
rank\[x\] = 2:表示x被f\[x\]吃

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 54014;
    
    int f[N], _rank[N];
    
    void init(int n);
    int get_f(int x);
    bool Merge(int d, int x, int y);
    
    int main(){
        int n, m, d, x, y, cnt;
        scanf("%d %d", &n, &m);
        init(n);
        cnt = 0;
        while(m--){
            scanf("%d %d %d", &d, &x, &y);
            if(x > n || y > n){
                cnt++;
                continue;
            }
            if(d == 2 && x == y){
                cnt++;
                continue;
            }
            if(!Merge(d, x, y)){
                cnt++;
            }
        }
        printf("%d\n", cnt);
        return 0;
    }
    void init(int n){
        for(int i = 1; i <= n; i++){
            f[i] = i, _rank[i] = 0;
        }
    }
    int get_f(int x){
        if(x == f[x]) return x;
        int fa = f[x];/*记录x未直接连接到根节点之前的父亲节点*/
        f[x] = get_f(f[x]);
        ///通过枚举x与父节点的_rank记录关系得到x与父节点的父节点的_rank记录关系
        if(_rank[x] == 0 && _rank[fa] == 0) _rank[x] = 0;
        else if(_rank[x] == 0 && _rank[fa] == 1) _rank[x] = 1;
        else if(_rank[x] == 0 && _rank[fa] == 2) _rank[x] = 2;
        else if(_rank[x] == 1 && _rank[fa] == 0) _rank[x] = 1;
        else if(_rank[x] == 1 && _rank[fa] == 1) _rank[x] = 2;
        else if(_rank[x] == 1 && _rank[fa] == 2) _rank[x] = 0;
        else if(_rank[x] == 2 && _rank[fa] == 0) _rank[x] = 2;
        else if(_rank[x] == 2 && _rank[fa] == 1) _rank[x] = 0;
        else if(_rank[x] == 2 && _rank[fa] == 2) _rank[x] = 1;
        return f[x];
    }
    bool Merge(int d, int x, int y){
        int t1 = get_f(x);
        int t2 = get_f(y);
        if(d == 1){
            if(t1 == t2){
                if(_rank[x] != _rank[y]) return false;
                else return true;
            }
            else {
                f[t1] = t2;
                ///通过枚举x与t1的_rank记录关系和y与t2的_rank记录关系得到t2与t1的_rank记录关系
                if(_rank[x] == 0 && _rank[y] == 0) _rank[t1] = 0;
                else if(_rank[x] == 0 && _rank[y] == 1) _rank[t1] = 1;
                else if(_rank[x] == 0 && _rank[y] == 2) _rank[t1] = 2;
                else if(_rank[x] == 1 && _rank[y] == 0) _rank[t1] = 2;
                else if(_rank[x] == 1 && _rank[y] == 1) _rank[t1] = 0;
                else if(_rank[x] == 1 && _rank[y] == 2) _rank[t1] = 1;
                else if(_rank[x] == 2 && _rank[y] == 0) _rank[t1] = 1;
                else if(_rank[x] == 2 && _rank[y] == 1) _rank[t1] = 2;
                else if(_rank[x] == 2 && _rank[y] == 2) _rank[t1] = 0;
                return true;
            }
        }
        else {
       /*d == 2*/
            if(t1 == t2){
                if(_rank[x] == 0 && _rank[y] != 2) return false;
                else if(_rank[x] == 1 && _rank[y] != 0) return false;
                else if(_rank[x] == 2 && _rank[y] != 1) return false;
                else return true;
            }
            else {
                f[t1] = t2;
                ///通过枚举x与t1的_rank记录关系和y与t2的_rank记录关系得到t2与t1的_rank记录关系
                if(_rank[x] == 0 && _rank[y] == 0) _rank[t1] = 1;
                else if(_rank[x] == 0 && _rank[y] == 1) _rank[t1] = 2;
                else if(_rank[x] == 0 && _rank[y] == 2) _rank[t1] = 0;
                else if(_rank[x] == 1 && _rank[y] == 0) _rank[t1] = 0;
                else if(_rank[x] == 1 && _rank[y] == 1) _rank[t1] = 1;
                else if(_rank[x] == 1 && _rank[y] == 2) _rank[t1] = 2;
                else if(_rank[x] == 2 && _rank[y] == 0) _rank[t1] = 2;
                else if(_rank[x] == 2 && _rank[y] == 1) _rank[t1] = 0;
                else if(_rank[x] == 2 && _rank[y] == 2) _rank[t1] = 1;
                return true;
            }
        }
    }

2.2[【Por Costel and the Match Gym - 100923H——vjudge题目链接】][Por Costel and the Match Gym - 100923H_vjudge]

##### 题意： #####

已知有n个战士，分属于两个红、蓝阵营，现输入m条敌对关系，当本条关系信息与之前的真的关系信息冲突，则认为本条关系信息为假(即先输入的敌对关系优先为真)

##### Input: #####

第一行输入T，代表T组测试数据  
每组测试数据第一行输入整数n和m，表示n个战士，m条敌对关系判断语句  
之后输入m行，每行含有整数x和y，表示认为x和y为敌对关系(即阵营不同)

##### Output: #####

输出m行，每行输出”YES”或”NO”(不含引号)，表示判断所得本条语句的真假

##### Sample Input: #####

1
    3 3
    1 2
    2 3
    1 3

##### Sample Output: #####

YES
    YES
    NO

题目分析：  
rank\[x\] = 0:表示x与f\[x\]为朋友(即属于同一阵营)  
rank\[x\] = 1:表示x与f\[x\]为敌人(即分属不同阵营)

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 104014;
    
    int f[N], _rank[N];
    
    void init(int n);
    int get_f(int x);
    bool Merge(int x, int y);
    
    int main(){
        freopen("meciul.in", "r", stdin);
        freopen("meciul.out", "w", stdout);
        int T, n, m, x, y;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            init(n);
            while(m--){
                scanf("%d %d", &x, &y);
                if(Merge(x, y)) printf("YES\n");
                else printf("NO\n");
            }
        }
        return 0;
    }
    void init(int n){
        for(int i = 1; i <= n; i++){
            f[i] = i, _rank[i] = 0;/*初始化：各自为根、皆为朋友*/
        }
    }
    int get_f(int x){
        if(x == f[x]) return x;
        int fa = f[x];/*记录未路径压缩(直接与根节点相连)前的父亲节点*/
        f[x] = get_f(f[x]);
        if(_rank[x] == 0 && _rank[fa] == 0) _rank[x] = 0;
        else if(_rank[x] == 0 && _rank[fa] == 1) _rank[x] = 1;
        else if(_rank[x] == 1 && _rank[fa] == 0) _rank[x] = 1;
        else if(_rank[x] == 1 && _rank[fa] == 1) _rank[x] = 0;
        return f[x];
    }
    bool Merge(int x, int y){
        int t1 = get_f(x);
        int t2 = get_f(y);
        if(t1 == t2){
       /*若x与y已存在关系，则通过x与根节点的_rank记录关系、y与根节点的_rank记录关系判断x与y是否为敌对关系*/
            if(_rank[x] == 0 && _rank[y] == 0) return false;
            if(_rank[x] == 0 && _rank[y] == 1) return true;
            if(_rank[x] == 1 && _rank[y] == 0) return true;
            if(_rank[x] == 1 && _rank[y] == 1) return false;
        }
        else {
       /*若x与y尚未存在关系，则根据x与其根节点t1的关系、y与其根节点t2的关系连接两个关系集合(连接两个关系集合的根)*/
            f[t1] = t2;
            if(_rank[x] == 0 && _rank[y] == 0) _rank[t1] = 1;
            else if(_rank[x] == 0 && _rank[y] == 1) _rank[t1] = 0;
            else if(_rank[x] == 1 && _rank[y] == 0) _rank[t1] = 0;
            else if(_rank[x] == 1 && _rank[y] == 1) _rank[t1] = 1;
        }
        return true;
    }

2.2例题感悟：1.基于并查集；2.认真仔细寻找rank\[i\]表示含义

[POJ - 1182_vjudge]: https://vjudge.net/problem/POJ-1182
[Por Costel and the Match Gym - 100923H_vjudge]: https://vjudge.net/problem/Gym-100923H