Codeforces Round #345 (Div. 2) E. Table Compression（并查集）传送门首先先从小到大排序，如果没有重复的元素，直接一个一个往上填即可，每一个数就等于当前行和列的最大值 + 1如果某一行或列上有重复的元素，就用并查集把他们连起来，很（不）显然，处
[BZOJ1594] [Usaco2008 Jan]猜数游戏（二分 + 并查集）传送门
题中重要信息，每堆草的数量都不一样。
可以思考一下，什么情况下才会出现矛盾。
1.如果两个区间的最小值一样，但是这两个区间没有交集，那么就出现矛盾。
2.如果两个区间
[BZOJ1604] [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居（好题）传送门
良心题解
#include <set>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100001
#define LL long long
#define INF (~(1 << 31))
us
[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门
蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs
[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）传送门
因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。
看了题解，，，，，，
这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样
[luoguP1196] 银河英雄传说（并查集）传送门
记录 up[x] 表示 x 上方有多少个
all[x] 表示当前连通的有多少个
find 的时候 和 合并的时候 更新一下即可
——代码
1 #include <cstdio>
2 #include <
[luoguP1111] 修复公路（并查集）传送门
呵呵的最小生成树
——代码
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4
5 #define N 100001
6
7 int n, m, sum;
8 int f
[luoguP2387] 魔法森林（LCT + 并查集）传送门
并查集真是一个判断连通的好东西！
连通性用并查集来搞。
把每一条边按照 a 为关键字从小到大排序。
那么直接枚举，动态维护 b 的最小生成树
用 a[i] + 1 ~ n 路径上
[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）传送门
1.贪心 + 优先队列
按照时间排序从前往后
很简单不多说
——代码
1 #include <queue>
2 #include <cstdio>
3 #include <iostream>
4 #include <algorithm>
[luoguP2342] 叠积木（并查集）传送门
up[i] 表示一个木块上面有多少个
all[i] 表示整个连通块内有多少个
那么 一个木块下面的木块个数为 all[root[i]] up[i] 1
注意：up[i] 可以在 find 函数中维护，而
[luoguP2147] [SDOI2008]Cave 洞穴勘测（并查集 || lct）传送门
1.并查集骗分（数据太水，比正解还快。。。）
我们知道，并查集有一步操作叫“路径压缩”，但是本题的并查集我们不能路径压缩，否则就无法进行Destroy操作。那每一步操作我们
[POJ1611]The Suspects（并查集）传送门
通过并查集统计集合个数，easy
——代码
1 #include <cstdio>
2 #include <iostream>
3 #define N 1000001
4
5 int n, m;
6 int f[N], num[N];
7
8 in
[POJ2912]Rochambeau（并查集）传送门
题意：
n个人分成三组，玩石头剪子布游戏，同一组的人只能出同样固定的的手势，其中有一个是裁判不属于任何组，可以出任意手势，给出m个信息x op y 表示x,y是从三个组里面随机
[HDU3038]How Many Answers Are Wrong（并查集）传送门
和某题类似，只不过奇偶换成了和。
——代码
1 #include <cstdio>
2 #include <iostream>
3 #define N 1000001
4
5 int n, m, ans;
6 int f[N], d[N];
7
[POJ1733]Parity game（并查集 + 离散化）传送门
题意：有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的
思路：如果我们知道[1,2][3,4][5,6]区间的信息，我们可以求出[1,
[POJ1703]Find them, Catch them（并查集）传送门
1.开两个并查集 f[x] 表示 x 的同类 f[x + n] 表示 x 的敌人
——代码
1 #include <cstdio>
2 #include <iostream>
3 #define N 200001
4
5 int T, n, m
[luoguP2024] 食物链（并查集）传送门
经典的并查集问题
对于这种问题，并查集需要分类
开3*n的并查集，其中x用来连接与x同类的，x+n用来连接x吃的，x+2*n用来连接x被吃的。
1 x y时，如果 x吃y 或 x被y吃，那么为
[luoguP1197] [JSOI2008]星球大战（并查集）传送门
思维！重要的是思维！
题目让删边，然而并查集不好删边（并！查！集！啊）
我们离线处理，从后往前添边，这样并查集就可以用了。
用并查集维护连通块个数即可。
——代码
1 #inclu
