复习写 find 和 unite

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 find_root（带路径压缩）和 unite（已经在同一块里就返回 false）。做两次合并之后输出那三件事。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 并查集连了两次之后写一个 Kruskal →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#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) {
    // TODO: 一路往上找根；顺手把沿途的点挂到爷爷上（p[x] = p[p[x]]）
    (void)p;
    return x;
}

bool unite(vector<int>& p, int a, int b) {
    // TODO: 两个根相同就返回 false；否则把一个根接到另一个根上，返回 true
    (void)p; (void)a; (void)b;
    return false;
}

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;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

复习写 find 和 unite

更多题目

全部评论