数据结构—并查集

基本信息

int p[N];

初始化： N个结点N个集合
合并： p[pa]=pb;

路径压缩find函数

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

按秩合并思路

维护一个size数组，代表每一个集合的大小，合并时小集合接到大集合上

维护信息

集合大小 size

每个点到根节点的距离(带权边) d

带权边find函数

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

扩展域 分类问题 时间和空间复杂度较带权边大

假设每个元素有两中类型
那么可以用1~n 表示该元素取第一类，用n+1~2n 表示该元素取第二类

给定条件 a 和 b不是一类，那么就把a和b+n合并到一个集合中，a+n和b合并到一个集合中
给定条件 a 和 b是一类，那么就把a和b合并到一个集合中，a+n和b+n合并到一个集合中

冲突条件：a！=b 结果a和b或者a+n和b+n在一个集合中，就冲突了

tips

并查集处理的是具有双向传递性的问题，遇到问题要能想到并查集
注意离散化，注意与其他问题的合并，比如 背包问题

难题

带权边：银河英雄传说
类别问题（带权边 or 扩展域）：食物链 奇偶游戏（这道题还不好看）
结合问题：搭配购买（01背包）