Algorithm12 并查集
[TOC]
并查集
模版-查看两个元素是否在一个集合中
https://www.luogu.com.cn/problem/P1551
题目大意：
1、findfa写法：return fa[x]==x?x:findfa(fa[x]);
- 如果
fa[x] == x，则代表这个节点就是代表这个集合的中心。 - 如果
fa[x] != x，继续递归往上找，findfa(fa[x])
「路径压缩，把一条线的树结构给压缩成一个矮宽胖的类似于dom树结构的样式」：return fa[x]==x?x:fa[x]=findfa(fa[x]);
- 通过在路径中对fa进行赋值，来保证路径上的fa都是那个父亲节点
- 可以看出指向关系的根。（类似题目找到某个节点的最终指向）
2、存放同个集合的关系：如果findfa(a)!=findafa(b)=>就可以直接让找到的顶上的直接赋给另一个的顶上。也即fa[findfa(a)]=findafa(b)或者fa[findfa(b)]=findafa(a)
#include <iostream>
using namespace std;
#define maxn 5005
int n, m, p, fa[maxn], ta, tb;
int findfa(int x){return fa[x] == x?x:findfa(fa[x]);}
int main() {
scanf("%d%d%d", &n, &m, &p);
// init
for (int i = 1; i <= n; ++i) fa[i]=i;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ta, &tb);
if (findfa(ta) != findfa(tb)) fa[findfa(tb)] = findfa(ta);
}
for (int i = 1; i <= p; ++i) {
scanf("%d%d", &ta, &tb);
if (findfa(ta) != findfa(tb)) printf("No\n");
else printf("Yes\n");
}
return 0;
}
模版-查看集合个数
https://www.luogu.com.cn/problem/P1536
题目大意：
1、
#include <iostream>
using namespace std;
#define maxn 1005
int n, m, fa[maxn], cnt, ta, tb;
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
int findfa(int x){return fa[x]==x?x:findfa(fa[x]);}
int main() {
while (scanf("%d%d", &n, &m) && n) {
cl(fa, 0);cnt = 0;
// init
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
scanf("%d%d", &ta, &tb);
if (findfa(ta) != findfa(tb)) fa[findfa(tb)] = findfa(ta);
}
for (int i = 1; i <= n; ++i) if (fa[i] == i) cnt++;
printf("%d\n", cnt-1);
}
return 0;
}
反集 & 敌对集
关键：敌对的敌对是朋友。运用反集解决。
https://www.luogu.com.cn/problem/P1892
#include <iostream>
using namespace std;
#define maxn 2020
int n, m, fa[maxn], ta, tb, cnt = 0;
char ch;
int findfa(int x){return fa[x]==x?x:findfa(fa[x]);}
int main() {
scanf("%d%d", &n, &m);
// init
for (int i = 1; i <= 2*n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
cin>>ch>>ta>>tb;
if (ch == 'F'){
fa[findfa(ta)] = findfa(tb);
} else{
fa[findfa(ta+n)] = findfa(tb);
fa[findfa(tb+n)] = findfa(ta);
}
}
for (int i = 1; i <= n; ++i)
if (fa[i] == i) cnt++;
printf("%d", cnt);
return 0;
}