算法背景

我们知道并查集，即 Disjoint-set data structure

是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示，其实也就是维护一颗森林， 操作的时间复杂度是一个接近常数的函数，，

并查集的合并和查询操作都很容易理解， 现在来复习一下并查集在集合关系方面的一些作用

算法思想

其实很久以前都学了这个了 一直没有碰到维护集合问题的题目，又给忘记了，这次又碰到了就来复习一下QAQ

以POJ1182食物链这道题为例，这个题目是维护三个集合的关系的，，，

“1 X Y”，表示X和Y是同类。
“2 X Y”，表示X吃Y。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

看到这个题目 我们知道物种之间只有吃与被吃的关系，那么这个关系其实就是一个如下图的环

那么我们现在把环状化为链状 即为 A -> B – > C – > A -> B -> C -> ……

这样每条链的关系就是一定的， 即定义一个节点到根节点的数组dis[i] mod 3 的距离判定关系

我们要寻找假话的次数，首先我们可以明确，两个节点一定是在一个集合（链）内才可以判断真假（不同的话怎么说也可以是真的啊），不同集合之间是无法相互影响的，

在同一个集合的，那么他们的关系，在mod3之后必定是一个定值（0，1，2）（一个食物链内的相对距离一定） 判断一下就好了

实现的算法的话 AC代码的注释已经带了，（虽然是很久以前写的吧

#include <bits/stdc++.h>
using namespace std;

#define N 50005

int pre[N], relation[N];

void init(int n)
{
    for(int i = 0;i <= n; i++) {
        pre[i] = i;
        relation[i] = 0;
    }
}
/*更新的同步，先将当前根节点与其根节点相连，然后更新其与根节点的关系
当前节点x与其根节点r的更新方法为：
    （x与其父节点的关系+父节点与根节点的关系）%3
    更新x节点的数据之前需要更新其父节点的数据
    更新的顺序为 ：从根节点向下直到更新到当前节点x的父节点 
*/
int find(int x)
{
    if(pre[x] == x) {    //x直接就是根节点 
        return x;
    }
    else {
        int temp = pre[x];  //将当前节点的父节点更新为根节点
        pre[x] = find(temp); //更新当前节点与根节点的关系,由X→X父节点，X父节点→根节点 
        //更新为X→X父根节点， 所以在此之前必须更新X父节点与根节点的关系
        relation[x] = (relation[x]+ relation[temp]) % 3; 
        return pre[x];
    } 
}
int main()
{
    int n, m, x, y, fx, fy, d, ans;
    scanf("%d%d",&n,&m);
        ans = 0;
        init(n);
        for(int i = 0;i < m; i++) {
            scanf("%d%d%d",&d,&x,&y);
            if(x>n || y>n) {
                ans++;
                continue;
            }
            if(d==2 && x==y) {
                ans++;
                continue;
            }
            fx = find(x);
            fy = find(y);
            if(fx == fy) {  // 属于同一个子集 
                //如果x，y同类那么它们对应的根节点应该一样
                if(d==1 && relation[x]!=relation[y]) {
                    ans++;
                }
                //如果不是同类，加入X与Y的关系后,X相对与根节点的关系(X根→Y，Y→X(即3-（d-1）=2)即X根→X)应该是不变的 
                // d = 2表示x-y=1,而y→x=3- (x→y)=2 
                 if(d==2 && relation[x]!=(relation[y]+2)%3) {
                    ans++;
                 } 
            }
            else {   //合并两个联通区域
                pre[fy] = fx; // y父的根节点更新为x的根
                //(d-1)为X与Y的关系，3-relation[y] 是y与y的根节点关系，relation[x]是其根节点与X的关系
                //X根 →X，X →Y根，即X根→Y根 
                relation[fy] = (relation[x]+(d-1)+(3-relation[y])) % 3;
            }
        }
        printf("%d\n",ans);
return 0;
}

算法应用

下面是几道关于这个算法具体实现的例题QAQ

CF396D 只有两个关系，很简单的判定 不过要加上map维护一下QAQ

https://blog.csdn.net/wang2332/article/details/78108485

——-未完待续———-