聊点学习的时候发现的好玩的东西

DS-V-1 并查集概述

并查集，是高级数据结构中最精巧的也是最好理解的一种数据结构。并查集描述的是一种 与其他不相交集合 之间的状态，每两个集合交集为空但可以实现集合内元素的传递相通， 适用于由时序并入的动态集合查找。

举一个最简单的例子，非连通图G的每一个连通区域的点都可以联合组成一个并查集——每一块连通区域之间互不相通，但是连通区域内的点可以到达该连通区域的任何一个点，符合并查集的特点。

并查集所维护的最经典的例子就是连通子图，算法生成最小生成树，从属关系以及树上。

并查集在路径压缩后可以以的真正时间复杂度判断目标点属于哪一个集合，相当的快速和适用。

DS-TR-1 一般并查集

一般并查集主要维护的就是上述综述中的 连通子图，算法生成最小生成树，从属关系以及树上 。

事实上，并查集更多是作为一个工具出现，单纯考察并查集的题目并不多。并查集维护最多的实例就是从属关系：牵一发而动全身，操作一个元素会连带着把所有的元素全部挪动( AT-20 Takahashi's Solitaire，虽然这个好像应该出现在DS-TR-3带权并查集 ) ；亦或是给定一个元素，询问其属于哪个元素的代表集合( （模板）并查集 )。

甚至，某一些奇奇怪怪的广搜都可以用并查集( AT-19 Ladder Takahashi )

事实上，并查集实现的过程很简单，关键的函数一共就两个——查询根节点以及集合元素合并。

对于初始化的时候，直接让每个就可以了。

对于查询函数，实现流程如下：

int getfather(int x)
{
    if(x!=father[x])return getfather(father[x]);
    return father[x];
}

这个是递归版本的，卡爆栈的非递归如下：

int getfather(int x)
{
    while(x!=father[x])
    {
        x=father[x];
    }
    return father[x];
}

其实不难理解这个行为。在这里，每一个都是的前驱

这一点很关键，也是有时候不能路径压缩的原因，father数组可以完整的保存下来集合初始时的样子以及每个元素的前驱指向。

对于集合元素的合并，就更简单了

void Union(int x,int y)
{
    x=getfather(x),y=getfather(y);
    if(x!=y)
    {father[x]=y;}
    return;
}

相当干脆的合并。

对于查询的优化可以采用压缩路径的方式，这样只有第一次查询时是的复杂度（退化成直线的时候），以后都是的菊花图。

int getfather(int x)
{
    if(x!=father[x])return father[x]=getfather(father[x]);
    return father[x];
}

DS-TR-2 种类并查集

现在，经过了 DS-TR-1 的教学，你已经可以熟练地管理哥伦比亚的南方监狱了。各个囚犯的档案和资料以及他们犯的什么类型的罪你都可以通过一般并查集解决了。

但是你现在还有一个问题解决不了：

杰斯顿来了之后煽动了这里的暴乱，哥伦比亚和莱茵生命用了很大的力气才把这群人收拾了一通。而作为新任监狱长的你不想出现上一次的情况，你想把之间有仇恨的囚犯分开。但是，你只知道谁仇恨谁，谁的朋友是谁，怎么样把互相不仇恨的人尽可能的放在一起呢？要知道，敌人的敌人就是朋友，朋友的敌人就是敌人，这帮人之间的关系错综复杂又相互纠缠，这个怎么办？

又或者，在一个生态系统中，捕食，捕食,捕食,现在有一群只含这三种动物的集群，如何判断他们之间的食物链关系？

上述的一般并查集只能描述集合之间相近关联（亲戚的亲戚还是亲戚，朋友的朋友还是朋友），却无法建立两个集合之间的对立关联（敌人的敌人是朋友，朋友的敌人是敌人）。如果并查集能把朋友都放在一边，把敌人都放在一边，那么上述两个题就会迎刃而解。

种类并查集，较为本质地说，维护的是一种循环对称的关系。

敌人的敌人就是朋友，很循环对称，没毛病。

回到监狱的问题，假设说有个囚犯，那么开一个大小的并查集，也就是正常大小的两倍，用来维护相对的朋友与敌人关系：

区间的并查集，维护的是南方监狱区关押囚犯的朋友关系以及其对于区关押的敌人关系。区间的并查集，维护的是南方监狱区关押囚犯的朋友关系以及其对于区关押的敌人关系。事实上，颠倒一下也可以。区间关押哪个区的敌人都行，只要两端区间属于不同的监狱就可以。

注意这个强调过的相对关系，后面要考。

那么假如说这个人中，1号和11号是敌人，而且相互之间仇恨度很高，那么他们就应当率先考虑不放到相同的监狱里面。所以，把1号放到1节点，11号放到节点，这样，我们就知道1和11的敌对关系，同时又能将二者不割裂的联系起来。由于相对关系的问题，同时要和合并。（因为 并查集的向量性 ,只表示1的敌人是11，没有将11的敌人是1也表现出来。)

那么此时，你又考察到了11号和4号是敌人，你重复了和

这个时候你有没有发现，4号作为朋友关系通过11号的敌人连接到了1号的并查集下面，是不是实现了敌人的敌人就是朋友？

那么此时，你维护出来的每一个并查集都是作为一个关系链出来的：

对于号囚犯所在的集合，凡是没有在区间的囚犯编号减去之后的编号囚犯都是的敌人，在区间内的都是的朋友，这就是一个种类并查集。

下面说的那个食物链问题，捕食，捕食,捕食，这是一个循环的关系，可以借助种类并查集来维护。这个时候就不是敌人的敌人就是朋友的循环关系了，而是一个捕食-捕食-捕食的单向闭环关系。（其实也可以进一步的把敌人的敌人就是朋友也解释成为一个敌人-敌人的单向闭环关系。）

那么开一个的并查集，维护的是同族关系，维护的是捕食关系，维护的是捕食-捕食关系，也就是有序环本环倒过来时的天敌关系（把环倒过来就成了天敌-天敌-天敌关系）

这样的时候，对于任意一个,它捕食的是,捕食它的的是

(符号代表)

所以维护捕食的关系的时候，就要维护下列的全部操作：

Union(a,b+n);
Union(a+n,b+2n);
Union(a+2n,b+3n);

确实挺不好理解的，但是这步必不可少。因为只有这样才能完整的串联起

的关系。

如果用下面的方式做，会累死的，因为边界条件真的很多，这种小规模的循环关系种类并查集会很精巧的用空间换时间。

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>father(10000001);
void init()
{
    for(int i=1;i<=3*n;i++)father[i]=i;
}
int getfather(int x)
{
    if(x!=father[x])
    {
        int fa=father[x];
        father[x]=getfather(father[x]);
    }
    return father[x];
}
void Union(int x,int y)
{
    x%=(3*n);
    y%=(3*n);
    x=getfather(x),y=getfather(y);
    if(x!=y)
    {
        father[x]=y;
    }
    return;
}
//[1,n]同类，[n+1,2n]捕食，[2n+1,3n]天敌
int main()
{
    cin>>n>>m;
    init();
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int t,a,b;
        cin>>t>>a>>b;
        if((t==2&&a==b)||(a>n||b>n))
        {
            ans++;continue;
        }
        switch(t)
        {
            case 1:
            if(getfather(a+n)==getfather(b)||getfather(a)==getfather(b+n))//跨单个n区间相连表明捕食关系
            {
                ans++;continue;
            }
            else
            {
                Union(a,b);
                Union(a+n,b+n);
                Union(a+2*n,b+2*n);
            }
            break;
            case 2:
            if(getfather(a)==getfather(b)||getfather(b+n)==getfather(a))
            {
                ans++;continue;
            }
            else
            {
                Union(a+n,b);
                Union(a+2*n,b+n);
                Union(a+3*n,b+2*n);
            }

        }
    }
    cout<<ans<<endl;
    system("pause");
    return 0;

}

DS-TR-3 带权并查集

带权并查集相较于普通并查集多了一步权值的操作。定义表示i到根节点的权值，随集合合并操作变化，表示的是集合元素针对根节点的信息。这个指向根节点的权值信息只说明子节点的，里面不包含根节点的任何信息。（这句话划重点，后面会考到）

按照之前的向量说法理解，如果说普通并查集表达的是一堆的单位向量，侧重于指向性说明，那么 带权并查集表达的的就是任意长度的向量，是真正意义的向量，表示存在从到根节点的一条向量，其长度为. 这样并查集就可以维护更多的信息，能够指出来根节点与查询节点之间的关系。（囊括了种类并查集的全部能力）。因此，带权并查集的核心能力就是维护多个元素之间的连通以及偏移关系，甚至可以维护多个偏移关系。

按照向量来理解，集合合并过程中的权值操作问题也就便于理解了：

void Union(int x,int y,int val)
{
    int fx=getfather(x),fy=getfather(y);
    if(fx!=fy)
    {
        father[fx]=fy;
        value[fx]=val-value[y]+value[x];//画两个向量式子极易理解
        return;
    }
}

查询问题加路径压缩

int getfather(int x)
{
    if(x!=father[x])
    {
        int fa=father[x];//father[x]会被压缩，所以需要手动记录前驱叠加
        father[x]=getfather(fatner[x]);
        value[x]+=value[fa];
    }
    return father[x];
}

一定要注意的是，权值信息只与查询点以及查询点到根节点之间的点有关，与根节点无关，下一道题这就是一个非常致命的问题，同时也就是带权并查集最经典的 模板题：

给定一段区间的和为x，问当前区间的和与前面的区间有没有冲突，如果有则是错误答案。最后输出错误答案数。
    eg: 
    [1, 10] = 5
    [1, 3] = 2
    [4, 10] = 4
    很显然第三个区间就是错误的，因为[1,3]+[4,10] != [1,10].

涉及到区间信息查询以及冲突判定的一般都是通过并查集快速维护，本题也不例外，这就是一道经典的带权并查集问题。但是本题的坑点在于，之前一直强调的权值不包括根节点的信息，事实上在本题的表现就是并查集必须维护的是一个左闭右开的区间，所以需要对右端点加一操作才能维护完整。如果两端点的根节点不合并，就可以出现；如果根节点重合后val还对不上，那就是错误的信息。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int ans = 0;
vector<int> valuerem(200001);
vector<int> father(200001);
vector<int> value;
void init()
{
    iota(father.begin() + 1, father.end(), 1L);
    value.clear();
    value = valuerem;
}
int getfather(int x) // 路径压缩的时候权值同时压缩
{
    if (x != father[x])
    {
        int fa = father[x];
        father[x] = getfather(fa); // 先定father后压缩
        value[x] += value[fa];     // 路径权值压缩,压缩的时候要注意保留原始记录，因为
        // father[x]此时已经完成压缩，不再是原值，中间会有错
    }
    return father[x];
}
void Union(int x, int y, int val) // 明确x向y压缩，就一定是x向y合并，不要根据父节点大小来调整压缩目标，明确向量特点
{
    int fx = getfather(x);
    int fy = getfather(y);
    if (fx != fy)
    {
        father[fx] = fy;
        value[fx] = val + value[y] - value[x];
    }
    else
    {
        if (value[x] - value[y] != val)
            ans++;
    }
}
signed main()
{
    while (cin >> n >> m)//原题没说明白，每次输入多组数据实例
    {
        ans = 0;
        init();
        int u, v, d, fa, fb;
        for (int i = 0; i < m; i++)
        {
            cin>>u>>v>>d;
            Union(u,v+1,d);
        }
        printf("%d\n", ans);
    }
    system("pause");
    return 0;
}

另一个比较典的就是 AT-20 Takahashi's Solitaire ，虽然暴力扫区间是可以的，但是这种带权值的思想非常可取。

再深层的以及例题留坑，待处理。