讲课之前

 我们不妨先考虑下傻瓜式合并，加入我们开一个数组表示某一个集合，那么在集合合并的时候，需要把每一个元素移动至对应集合，合并复杂度O(n),查找复杂度O(n)。
我们能优化合并么？当然可以，用链表或者STL的list。

由于不支持随机存取，那么查找的复杂度还是O(n)。怎么优化查找，那就用并查集了

概述

 并查集顾名思义就是有“合并集合”和“查找集合”两种操作的关于数据结构的一种算法。

操作

初始化：

1
2
3
4
5
6
7
8
void init() 
{
    for(int i=0; i<N; i++)
    {
        par[i] = i;
        rank[i] = 1;
    }
}

查找：

1
2
3
4
5
int find(int x)
{
    return par[x] = find(par[x]);
}

合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void unite(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x==y) return ;
    if(rank[x]<rank[y])
    {
        par[x] = y;
    }
    else{
        par[y] = x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

判同：

1
2
3
4
bool same(int x,int y)
{
    return find(x) == find(y);
}

复杂度

 复杂度很玄，算法导论有证明。路径压缩好写，但是大多数人不写启发式合并，可能会被卡。。

裸并查套路

 并查集大约有以下特征但不局限于此。

  • 维护区域信息 KRUSKAL最小生成树算法，无向图的环，无向图连通分量，线段覆盖，区域联通等

  • 维护关系 拆点，lCA，虚拟图，等价类等

  • 破坏关系 拆边，逆向并查集等//正难则反

例题

L1

TOJ2469 Friends

题目描述：有n个人，m对朋友关系，朋友关系对称且可传递，求有几个朋友圈。

分析：事实上是求一个无向图的连通分量数，并查集轻松搞定。

TOJ3294 Building Blcok

题目描述：一开始有n个Block，分别放置在地面上，有P个操作，操作有两种类型：

M a b如果a,b没有在一个Block组里，把包含a Block的Block组放在包含b的Block组之上。

C a 输出有多少个Block被压在了a之下。

类似题目 排队询问间隔

划分等价类

scau 1138 代码等式 //题目链接实在搞不到

Description

 一个代码等式就是形如 $ x{1}x{2} \dot x{i} = y{1}y{2} \dot y{j} $ ，这里$ x{i} $和 $ y{j} $是二进制的数字（0或1）或者是一个变量（如英语中的小写字母）。每一个变量都是一个有固定长度的二进制代码。

例如：

a,b,c,d,e是变且它们的长度分别是4,2,4,4,2。考虑等式：1bad1 = acbe ，这个等式共有16组解。现要求任给一个等式，计算一共有多少组解。（变量最多26个，长度和不超过10000）

输入格式

 第一行数N为变量个数；第二行N个数，为每个变量的位数；第三行为一个等式

输出格式

 输出解的个数，无解输出0

输入样例

5
4 2 4 4 2
1bad1=acbe

输出样例

16

code[vs] 2597 团伙

描述

 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是A的朋友的朋友是A的朋友；A的敌人的敌人也是A的朋友。

 两个强盗是同一伙的当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你至多有多少个强盗团伙。

输入格式

 输入的第一行为N(2<=N<=1000)，表示强盗的个数（从1编号到N）。第二行M(1<=M<=5000)，表示信息条数。以下M行，每行可能是F p q或是E p q，分别表示p和q是朋友，或是敌人。假设输入不会产生矛盾

输出格式

 输出只有一行，表示最大可能的团伙数。

朋友很好处理。
很明显一点，一个人的敌人一定是一个集合。
设e[x] 为x的敌人集合，如果出现p,q是敌人 那么就把e[p]与q合并 e[q]与p合并
合并次数为T 那么ans为N-T
改变询问内容 变为维护关系
维护区域

可以搞一些BFS求联通水域//
线段覆盖问题//

维护关系

POJ 食物链 把团伙关系加强版