并查集
用处
- 合并两个集合
- 查看两个元素是否是在一个集合之中
基本原理
每个集合用一棵树来表示，树根的编号是整个集合的编号。每个节点存储 x 的父节点，p [ x ] 表示 x 的父节点。
问题
- 如何判断树根 if ( p [ x ] == x )
- 求 x 的集合编号 while ( p [ x ] != x) x = p [ x ]
- 如何将两个集合合并 p [ x ] 是 x 的集合编号，p [ y ] 是 y 的集合编号 ；p [ x ] = y ;
模板
(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点 + 路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
如何理解 find ( ) 函数
p[x]中储存的是每个节点的父节点，一开始并不是树状的，而是一个个单独的节点，每个节点都是根节点，都有集合编号，然后通过不断的合并才形成的树状结构
例1.合并集合
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作共有两种：
- “M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
- “Q a b”，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100000;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n, m;
// 存储父节点
int f[N];
void init(){
for(int i = 0; i < n; i ++ ){
f[i] = i;
}
}
// 核心操作 : 路径压缩
// 查询根节点的优化，将所有的父节点下面的点指向根节点
int getf(int x){
if(f[x] == x) return f[x];
else{
f[x] = getf(f[x]);
return f[x];
}
}
// 合并两个集合，x 集合的编号的父节点是 y 集合的根节点
void merge(int x, int y){
if(getf(x) != getf(y)) f[getf(y)] = getf(x);
}
int main()
{
cin >> n >> m;
init();
for(int i = 0; i < m; i ++ ){
char op;
int x, y;
cin >> op >> x >> y;
if(op == 'M'){
merge(x, y);
}
else if(op == 'Q'){
if(getf(x) == getf(y)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}
例2.连通块中点的数量
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
- “C a b”，在点a和点b之间连一条边，a和b可能相等；
- “Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
- “Q2 a”，询问点a所在连通块中点的数量；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。
输出格式
对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。
对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
代码样例
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100000;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n, m;
int f[N], cnt[N];
void init(){
for(int i = 1; i <= n; i ++ ){
f[i] = i;
cnt[i] = 1;
}
}
int getf(int x){
if(f[x] == x) return x;
else{
f[x] = getf(f[x]);
return f[x];
}
}
void merge(int x, int y){
if(getf(x) != getf(y)){
//维护cnt数组的时候，一定要先维护，在进行合并
cnt[getf(y)] += cnt[getf(x)];
f[getf(x)] = getf(y);
}
}
int main()
{
cin >> n >> m;
init();
for(int i = 0; i < m; i ++ ){
string op;
int x, y;
cin >> op;
if(op == "C"){
cin >> x >> y;
merge(x, y);
}
else if(op == "Q1"){
cin >> x >> y;
if(getf(x) == getf(y)) cout << "Yes" << endl;
else cout << "No" << endl;
}
else if(op == "Q2"){
cin >> x;
cout << cnt[getf(x)] << endl;
}
}
return 0;
}
AcWing 240.食物链
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
输入格式
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3
代码样例
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100000;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}
int n, k;
int f[N], cnt[N];
void init(){
for(int i = 1; i <= n; i ++ ){
f[i] = i;
}
}
int getf(int x){
if(f[x] == x) return x;
else {
int t = getf(f[x]);
cnt[x] += cnt[f[x]];
f[x] = t;
return f[x];
}
}
int main()
{
cin >> n >> k;
init();
int res = 0;
while(k -- ){
int d, x, y;
cin >> d >> x >> y;
//大于范围是谎话
if(x > n || y > n) res ++ ;
else{
int px = getf(x), py = getf(y);
if(d == 1){
//同类吃同类是谎话
if(px == py && (cnt[x] - cnt[y]) % 3) res ++ ;
else if(px != py){
f[px] = py;
cnt[px] = cnt[y] - cnt[x];
}
}
else{
if(px == py && (cnt[x] - cnt[y] - 1) % 3) res ++ ;
else if(px != py){
f[px] = py;
cnt[px] = cnt[y] + 1 - cnt[x];
}
}
}
}
cout << res << endl;
return 0;
}