并查集连了两次之后
五个点各自一块。先 unite(0, 2),再 unite(3, 4)。运行下面这段程序,看三件事:0 和 2 连通了吗、0 和 3 连通了吗、现在还剩几块:
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1000000000; // 走不到的点记这个值,输出时写成 -1
using Graph = vector<vector<pair<int, int>>>; // g[u] 里放 (邻居 v, 边权 w)
vector<int> make_set(int n) {
vector<int> p(n);
for (int i = 0; i < n; i++) p[i] = i;
return p;
}
int find_root(vector<int>& p, int x) {
while (p[x] != x) {
p[x] = p[p[x]]; // 路径压缩:挂到爷爷上
x = p[x];
}
return x;
}
bool unite(vector<int>& p, int a, int b) {
// 两端已在同一块里就返回 false(这条边会成环)
int ra = find_root(p, a), rb = find_root(p, b);
if (ra == rb) return false;
p[ra] = rb;
return true;
}
int main() {
vector<int> p = make_set(5);
unite(p, 0, 2);
unite(p, 3, 4);
set<int> roots;
for (int u = 0; u < 5; u++) roots.insert(find_root(p, u));
cout << boolalpha << (find_root(p, 0) == find_root(p, 2)) << "/" << (find_root(p, 0) == find_root(p, 3)) << "/"
<< roots.size() << endl;
}
(本题用 g++ -std=c++17 -O0 编译。)
全部评论