并查集
并查集是通过数组p和find函数，实现集合之间的合并，元素查询的数据结构
======================================
性质
1.p和p是相连的;
2.如果p和q是相连的，那么q和p也是相连的
3.如果p和q是相连且q和r是相连，那么p和r也相连
三个操作：
1.合并两个集合
2.查找某个元素的祖宗节点
3.查询某元素到根节点的距离
两个优化：
1.路径压缩 -> 时间复杂度降到o(logn)
2.按秩合并 -> 时间复杂度降到o(logn)
若两者一起使用 -> 线性
三个维护：
1.记录每个集合的大小(绑定到跟节点)
2.记录每个点到跟节点的距离(绑定到每个元素)
由此可延伸出
维护点之间的距离（见例题）
3.记录连通片的数量
======================================
id[x]表示节点x的父节点，跟节点的父节点就是自己，即
如果x是跟节点，则id[x] = x
初始时，所有点都各自在一个集合，即对于每个点n,
初始化成id[n] = n
实现
#include <iostream>
#include <cstring>
using namespace std;
/*
用一个以触点为索引的数组 id 作为基本数据结构来表示所有分量
使用分量中的某个触点的名称作为分量标识符，即每个分量都是由他的触点之一表示的
一开始有N个触点，每个触点构成一个只含有他自己的分量，初始：id[i] = i
connected 的实现：find(p) == find(q)
维护两个实例变量：连通分量个数和数组id
对于N个触点，加权quick-union算法构造的森林中任意节点的深度最多是 lgN
且森林中大小为 k 的树的高度最多为 lgk
*/
class unionFind{
public:
unionFind(int size);
~unionFind();
void union_node(int p, int q); //归并两个分量
int find(int p); //返回所在连通分量的标识符
bool connected(int p, int q); //判断两个点是否在同一个分量中
int count(); //返回连通分量的数量
private:
int num; //连通分量的数量
int *id;
int *dist; //点到根节点距离
int *rootSize; //记录各个跟节点对应的分量大小
};
unionFind::unionFind(int size){
num = size;
id = new int[size];
rootSize = new int[size];
for (int i = 0; i < size; i ++){
id[i] = i;
}
for (int i = 0; i < size; i ++){
rootSize[i] = 1;
}
}
unionFind::~unionFind(){
delete[] id;
num = 0;
}
int unionFind::count(){
return num;
}
bool unionFind::connected(int p, int q){
return find(p) == find(q);
}
int unionFind::find(int p){
if (p != id[p]) p = find(id[p]); //路径压缩
return p;
}
/* 无路径压缩版
int unionFind::find(int p){
while (p != id[p]) p = id[p];
return p;
}
*/
/*记录每个连通片的大小
将较小的连通片连接到较大的连通片
加权-quick-union算法*/
void unionFind::union_node(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if (qRoot == pRoot) return;
if (rootSize[pRoot] < rootSize[qRoot]){
id[pRoot] = qRoot;
rootSize[qRoot] += rootSize[pRoot];
}
else{
id[qRoot] = pRoot;
rootSize[pRoot] += rootSize[qRoot];
}
num --;
}
int main(){
int size;
cin >> size;
unionFind uF(size);
//输入-1结束
int p, q;
cout << "Please input to connect components:" << endl;
while (cin >> p >> q && p != -1){
if (!uF.connected(p, q)){
uF.union_node(p, q);
}
}
cout << "Please input to judge components:" << endl;
while (cin >> p >> q && p != -1){
if (uF.connected(p, q)){
cout << "[" << p << "]" << " [" << q << "] Root: " << uF.find(p) << endl;
}else{
cout << "[" << p << "]" << " [" << q << "] " << " No" << endl;
}
}
cout << endl << "components: " << uF.count() << endl;
}
===========================
例题
0.银河英雄传说
题目
有一个划分成 N 列的星际战场，各列依次编号为 1,2, …， N
有 N 艘战舰，也依次编号为 1,2, …, N，其中第 i 号战舰处于第 i 列
有 M 条指令，每条指令格式为以下两种之一:
M i j 表示让第 i 号战舰所在列的战舰保持原有顺序，接在第 j 号战舰所在列的尾部
Ci j 表示询问第 i 号战舰与第 j 号战舰是否处于同一列中，若是，它们之间间隔了多少艘战舰。
N <= 30000, M <= 5e5
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.奇偶游戏
题目
小A和小B在玩一个游戏
首先，小A写了一个由0和1组成的序列s, 长度为N
然后，小 B 向小 A 提出 M 个问题
在每个问题中，小 B 指定两个数 l 和 r
小 A 回答 S[l~r] 中有奇数个 1 还是偶数个 1
小 A 有可能撒谎
例如，小 A 曾经回答过 S[1~3] 中有奇数个1，S[4~6] 中有偶数个 1
现在又回答 S[1~6] 中有偶数个 1，显然矛盾
请你帮助小 B 检查这 M 个答案
并指出在至少多少个回答之后可以确定小 A 一定 在报谎
N <= 1e9, M<=10000。
知识点
并查集(带边权)+前缀和+离散化+异或运算
思路
构造数组s
s
i
= a
1
+ a
2
+ … + a
i
(a = 1 / 0)
a
i
= | s
i
– s
i-1
|
若s
i
和 s
i-1
奇偶性相同 a
i
=0
若s
i
和 s
i-1
奇偶性不同 a
i
=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;
}
End