并查集基础

并查集是一种很有趣的数据结构. 最清楚说明并查集的例子是亲戚问题, 今天是大年初二, 四处亲戚来拜年, 学习并查集真是应景.

并查集是我新年学的第一种数据结构. 之前接触它的时候觉得这个名字的DS很复杂, 因为不了解且很难望文生义, 不过接触了之后, 发现比较简单的.

所以, 学算法千万不能畏难, 因为各种算法都不会是简单的, 但也不会是很难的. 只要你多去做做, 自己写写, 理解了就不难了.

下面给出洛谷网的一个并查集模板, 这里有并查集最基本的操作

#include <bits/stdc++.h> using namespace std; int f[10005]; void init(int n) //初始化数组, 非常重要!!! { for(int i = 1; i <= n; ++i) f[i] = i; } int find(int n) //查找所属集合(祖先)的函数 { return n == f[n] ? n : f[n] = find(f[n]); //路径压缩 } void merge(int x, int y) //合并集合的函数 { x = find(x), y = find(y); if(x != y) { f[y] = x; } } void getData(int m) { int a, b, c; for(int i = 0; i < m; ++i) { cin >> a >> b >> c; if(a == 1) merge(b, c); else if(find(b) == find(c)) cout << "Y\n"; else cout << "N\n"; } } int main() { int n, m; cin >> n >> m; init(n); //初始化数组, 很重要! getData(m); //get数据 }

上面这个模板包含了并查集最基本的建立, 合并, 查找操作, 写并查集的时候牢记这几个操作就好, 一个一个写出来.

并查集的一个优化是路径压缩, 各种资料都有提到. 我就不介绍并查集了, 介绍也介绍不清楚.

亲戚问题

#include <bits/stdc++.h> using namespace std; int f[5005]; void init(int n) { for(int i = 0; i <= n; ++i) f[i] = i; } int find(int n) { return (n == f[n] ? n : (f[n] = find(f[n]))); } void merge(int x, int y) { x = find(x), y = find(y); if(x != y) { f[y] = find(x); } } void getData(int n) { //cout << "1\n"; int x, y; for(int i = 0; i < n; ++i) { cin >> x >> y; merge(x, y); } //cout << "2\n"; } void ask(int p) { int x, y; for(int i = 0; i < p; ++i) { cin >> x >> y; if(find(x) == find(y)) { cout << "Yes\n"; } else cout << "No\n"; } } int main() { int n, m, p; cin >> n >> m >> p; init(n); getData(m); ask(p); }

村村通

AC代码

#include <bits/stdc++.h> using namespace std; int f[1005]; void init(int n) { for(int i = 1; i <= n; ++i) f[i] = i; } int find(int n) { return n == f[n] ? f[n] : f[n] = find(f[n]); } void merge(int x, int y) { x = find(x), y = find(y); if(x != y) { f[y] = x; } } void getData(int m) { int x, y; for(int i = 0; i < m; ++i) { cin >> x >> y; merge(x, y); } } int judge(int n) { int cnt = 0; for(int i = 1; i <= n; ++i) { if(f[i] == i) cnt++; } return cnt - 1; } int main() { int n, m; while((cin >> n) && n) { cin >> m; init(n); getData(m); cout << judge(n)<< endl; } }