并查集
写在开头：配合例题食用效果极佳！
并查集是通过数组p和find函数，实现集合之间的合并，元素查询的数据结构
两个操作：
1.合并两个集合
2.查找某个元素的祖宗节点
两个优化：
1.路径压缩 -> 时间复杂度降到o(logn)
2.按秩合并 -> 时间复杂度降到o(logn)
若两者一起使用 -> 线性
两个维护：
1.记录每个集合的大小(绑定到跟节点)
2.记录每个点到跟节点的距离(绑定到每个元素)
由此可延伸出维护点之间的距离(例023)和关系(例1)
p[x]表示节点x的父节点，跟节点的父节点就是自己，即如果x是跟节点，则p[x] = x
初始时，所有点都各自在一个集合，即对于每个点n,初始化成p[n] = n
初始化：
for ( int i = 1; i <= n; i ++ ) p[i] = i;
find函数（含路径压缩）：
回溯的时候，令每个点的p[n]等于跟节点，即find函数执行完后，集合内所有点指向跟节点
int find(int x){
if ( p[x] != x ) p[x] = find(p[x]); 如果该点不是跟节点，就继续递归
//回溯的时候，令每个点的p[n]等于跟节点，即find函数执行完后，集合内所有点指向跟节点
return p[x]; //返回跟节点
}
判断两个点是否在一个集合内：
if ( find(a) == find(b) ) cout << "Yes";
else cout << "No";
合并两个集合：
让其中一个集合的跟节点指向另一个集合的跟节点
int pa = find(a), int pb = find(b); //找a和b的跟节点
p[pa] = pb; //让a的跟节点指向b的跟节点
===========================
例题
0.银河英雄传说
https://www.acwing.com/problem/content/240/
1.判断两点是否在同一集合
2.计算两点间的距离
-> 维护两点间的距离
题目要求将一列战舰接到另一列战舰的排尾，但在实现上，将集合接到另一个集合的排头，并更新被挪动集合的点到新跟节点的距离
每次操作，更新被挪动的每个点到新跟节点的距离，即加上挪到的集合的size
实现：
每个点存距离d，即这个点到父节点的距离
若把a集合挪到b集合后面
-> d[pa] = size[pb] 更新a集合的跟节点到父节点(即b集合的跟节点)的距离
size[pb] += size[pa] 更新新集合的大小
find函数中，递归到跟节点后，从跟节点开始回溯，令d[x]等于x到父节点的距离，加上父节点到跟节点的距离，并让回溯到的点指向跟节点，即更新了x到跟节点的距离
两艘战舰间的距离：
if ( d[x] != d[y] ) cout << abs(d[x] - d[y] ) - 1 << endl;
else cout << 0 << endl;
#include <iostream>
using namespace std;
const int N = 30010;
int p[N], d[N], s[N], m;
int find(int x)
{
if ( x != p[x] )
{
int root = find(p[x]); //递归到跟节点
d[x] += d[p[x]]; //回溯，从跟节点开始，d[x]等于x到父节点的距离加父节点到跟节点的距离
p[x] = root; //回溯，让每个点直接指向跟节点
}
return p[x];
}
int main()
{
cin >> m;
for ( int i = 1; i < N; i ++ ) //不能等于N，数组会越界，易错
{
d[i] = 0; //到跟节点的距离
s[i] = 1; //集合中点的数量
p[i] = i; //集合
}
while ( m -- )
{
int a, b;
char op[2];
cin >> op >> a >> b;
if ( op[0] == 'M' )
{
int pa = find(a), pb = find(b);
if ( pa != pb )
{
d[pa] = s[pb]; //pa到新跟节点的距离为s[pb]，再用d[a]跟新a下面的点
s[pb] += s[pa]; //更新新集合的点的数量
p[pa] = pb;
}
}
else
{
int pa = find(a), pb = find(b);
if ( pa != pb ) cout << -1 << endl;
else cout << max(0, abs(d[a] - d[b]) - 1) << endl;
}
}
return 0;
}
===========================
1.奇偶游戏
https://www.acwing.com/problem/content/241/
并查集(带边权)+前缀和+离散化+异或运算
构造数组s
si = a1 + a2 + … + ai (a = 1 / 0)
ai = | si - si-1 |
若si 和 si-1 奇偶性相同 ai=0
若si 和 si-1 奇偶性不同 ai=1
故能构造出01数列，满足条件
s[l~r]中有奇数个1
-> s[r] - s[l-1] 为奇数
-> s[r]与s[l-1]奇偶性不同
s[l~r]中有偶数个1
-> s[r] - s[l-1] 为偶数
-> s[r]与s[l-1]奇偶性相同
若每次输入的奇偶性与存在的奇偶性无矛盾 <-> 问题无矛盾
做法：
维护相对关系，每个点存他和跟节点的关系d[x]
通过每个点与跟节点的相对关系，得到每个点间的关系
d[x]存0/1，表示x和px的关系
若d[x] = 0，表示x与px同类，否则不同类
对于点x和y：
若d[x] + d[y]为偶数(d[x]^d[y] = 0)
-> 则x与根同类，y与根同类 -> x与y同类(奇偶性相同)
若d[x] + d[y]为奇数(d[x]^d[y] = 1)
-> x(y)与根同类，y(x)与根不同类 -> x与y不同类(奇偶性不同)
1）若告诉我们x和y是同类
若px = py
-> 说明x和y在同一个集合中
(点x)o->o->...-> o(跟节点) <-o<-o<-o(点y)
若d[x]^d[y] = 0 -> x与y同类 -> 无矛盾
若d[x]^d[y] = 1 -> x与y异类 -> 有矛盾
若px != py
将x集合合并到y集合
x和y是同类 -> d[x] + d[px] + d[y]为偶数 (d[px]表示px到py的距离)
-> d[px] = d[x]异或d[y]异或0 (该取值可满足上一行要求)
2）若告诉我们x和y是异类
若px = py
-> 说明x和y在同一个集合
若d[x]^d[y] = 0 -> x和y是同类 -> 有矛盾
若d[x]^d[y] = 1 -> x和y是异类 -> 无矛盾
若px != py
将x集合合并到y集合
x和y是异类 -> d[x] + d[px] + d[y]为奇数
d[px] = d[x]异或d[y]异或1 (该取值可满足上一行要求)
#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int N = 20010;
int p[N], d[N], n, m, cnt;
unordered_map<int, int> mp;
int get(int x)
{
if ( !mp.count(x) ) mp[x] = ++ cnt;
return mp[x];
}
int find(int x)
{
if ( x != p[x] )
{
int root = find(p[x]);
d[x] += d[p[x]] % 2; //防止数据越界，也可以这里不mod2，下面判断时(...mod2+2)%2转为正数(奇偶不影响)
p[x] = root;
}
return p[x];
}
int main()
{
cin >> n >> m;
for ( int i = 1; i <= N; i ++ ) p[i] = i;
int res = m;
for ( int i = 1; i <= m; i ++ )
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b); //对于虚拟数组a的前缀和，为s[l-1]到s[r]
int t = 0;
if ( type == "odd" ) t = 1; //用t控制奇偶性，巧妙运用
int pa = find(a), pb = find(b);
if ( pa == pb )
{
if ( (d[a] + d[b]) % 2 != t ) //如果奇偶性不匹配
{
res = i - 1;
break;
}
}
else
{
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t; //按输入处理d[a] d[b]的关系
}
}
cout << res;
return 0;
}
===========================
2.格子游戏
https://www.acwing.com/problem/content/1252/
·将格子的每个点抽象成图论中的点
·出现圈的条件：当前连接的点（画的边的两个端点），已经在同一个连通块当中
·把二维坐标转换为一维坐标（x和y都从0开始，二维数组大小是n*n）：
(x, y) ->对应下标为 x * n + y
若x从1开始
(x, y) -> 对应下标为(x - 1) * n + y
(x - 1) * n表示其该行的前边几行的的数字个数，再加上y即可得到
#include <iostream>
#include <cstring>
using namespace std;
const int N = 40010;
int f[N], p[N], n, m, res;
int find(int x) //找祖宗节点
{
if ( p[x] != x ) p[x] = find(p[x]);
return p[x];
}
int get(int x, int y) //将二维数组转换为一维
{
return x * n + y;
}
int main()
{
cin >> n >> m;
for ( int i = 0; i < N; i ++ ) p[i] = i; //初始化每一个集合
for ( int i = 1; i <= m; i ++ )
{
int x, y, a, b; //x,y是当前坐标 a,b是对应一维数组的位置
string op;
cin >> x >> y >> op;
x --, y --; //下标从0开始
a = get(x, y);
if ( op == "D" ) b = get(x + 1, y);
else b = get(x, y + 1);
int pa = find(a), pb = find(b);
if ( pa == pb ) //如果当前两个点在同一个集合中，游戏停止
{
res = i;
break;
}
p[pa] = pb; //如果当前两个点不在同一个集合，将他们放到同一个集合
}
if ( res != 0 ) cout << res << endl;
else puts("draw");
return 0;
}
===========================
3.食物链
每次合并集合a，b的时候
用d[pa]维护a和b的关系
若a,b在一个集合
若(d[a] - d[b]) % 3 = 1 -> a吃b
若(d[a] - d[b]) % 3 = 0 -> ab同类
若a,b不在同一集合
若a吃b，则令d[pa] = d[b] - d[a] + 1 -> 以满足(d[a] + d[pa] - d[b]) % 3 = 1
若ab同类，则令d[pa] = d[b] - d[a] -> 以满足(d[a] + d[pa] - d[b]) % 3 = 0;
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], d[N], n, m, res;
int find(int x)
{
if ( x != p[x] )
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x]= root;
}
return p[x];
}
int main()
{
cin >> n >> m;
for ( int i = 1; i <= n; i ++ ) p[i] = i;
while ( m -- )
{
int op, a, b;
cin >> op >> a >> b;
if ( a > n || b > n ) res ++;
else
{
int pa = find(a), pb = find(b);
if ( op == 1 )
{
if ( pa == pb && (d[a] - d[b]) % 3 ) res ++;
else if ( pa != pb )
{
p[pa] = pb;
d[pa] = d[b] - d[a];
}
}
else
{
if ( pa == pb && (d[a] - d[b] - 1) % 3 ) res ++;
else if ( pa != pb )
{
p[pa] = pb;
d[pa] = d[b] - d[a] + 1;
}
}
}
}
cout << res;
return 0;
}