第 13 章　数据结构与算法补遗

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

void mergeSort(std::vector<int>& a, int l, int r, std::vector<int>& buf) {
    if (r - l <= 1) { return; }
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid, buf);
    mergeSort(a, mid, r, buf);
    int i = l, j = mid, k = l;
    while (i < mid && j < r) { buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; }
    while (i < mid) { buf[k++] = a[i++]; }
    while (j < r) { buf[k++] = a[j++]; }
    for (int t = l; t < r; ++t) { a[t] = buf[t]; }
}

int main() {
    int n{};
    std::cin >> n;
    std::vector<int> a(static_cast<std::size_t>(n));
    for (int i = 0; i < n; ++i) { std::cin >> a[i]; }

    std::vector<int> buf(a.size());
    mergeSort(a, 0, n, buf);
    for (int i = 0; i < n; ++i) { std::cout << a[i] << (i + 1 == n ? '\n' : ' '); }

    std::mt19937 gen(12345);                 // 固定种子，结果可复现
    std::uniform_int_distribution<int> dist(-1000, 1000);
    for (int round = 0; round < 200; ++round) {
        int len = 1 + round % 50;
        std::vector<int> mine(static_cast<std::size_t>(len)), ref;
        for (int i = 0; i < len; ++i) { mine[i] = dist(gen); }
        ref = mine;
        std::vector<int> tmp(mine.size());
        mergeSort(mine, 0, len, tmp);
        std::sort(ref.begin(), ref.end());
        assert(mine == ref);
    }
    std::cout << "ok\n";
    return 0;
}

解析　对拍是验证自己实现的通用手段：同一份随机输入喂给两个实现，逐元素比较；固定种子保证失败可复现。

#include <iostream>
#include <memory>

struct Node {
    int value{};
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) { }
};

void insert(std::unique_ptr<Node>& root, int v) {
    if (!root) { root = std::make_unique<Node>(v); return; }
    if (v < root->value) { insert(root->left, v); }
    else if (v > root->value) { insert(root->right, v); }
    // 相等：忽略，保持集合语义
}

void inorder(const std::unique_ptr<Node>& root, bool& first) {
    if (!root) { return; }
    inorder(root->left, first);
    std::cout << (first ? "" : " ") << root->value;
    first = false;
    inorder(root->right, first);
}

const Node* minNode(const std::unique_ptr<Node>& root) {
    const Node* p = root.get();
    while (p && p->left) { p = p->left.get(); }
    return p;
}

const Node* maxNode(const std::unique_ptr<Node>& root) {
    const Node* p = root.get();
    while (p && p->right) { p = p->right.get(); }
    return p;
}

int main() {
    int n{};
    std::cin >> n;
    std::unique_ptr<Node> root;
    for (int i = 0; i < n; ++i) {
        int x{};
        std::cin >> x;
        insert(root, x);
    }
    bool first = true;
    inorder(root, first);
    std::cout << '\n';
    std::cout << "min=" << minNode(root)->value << '\n';
    std::cout << "max=" << maxNode(root)->value << '\n';
    return 0;
}

解析　unique_ptr 让整棵树在 root 析构时自动递归释放，不需要手写析构函数；注意树很深时递归释放同样有爆栈风险。

#include <iostream>
#include <queue>
#include <vector>

void dfs(int u, const std::vector<std::vector<int>>& g, std::vector<char>& vis) {
    vis[u] = 1;
    for (int v : g[u]) {
        if (!vis[v]) { dfs(v, g, vis); }
    }
}

int main() {
    int n{}, m{};
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u{}, v{};
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 1) 连通块计数（DFS）
    std::vector<char> vis(n, 0);
    int components = 0;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            ++components;
            dfs(i, g, vis);
        }
    }
    std::cout << "components=" << components << '\n';

    // 2) 无权最短路（BFS）
    std::vector<int> dist(n, -1);
    std::queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    std::cout << "dist=" << dist[n - 1] << '\n';
    return 0;
}

解析　BFS 里“入队即标记”是保证每个点只入队一次的关键；如果改成出队时标记，同一个点会被重复入队，复杂度退化甚至出错。

#include <iostream>
#include <utility>
#include <vector>

struct DSU {
    std::vector<int> parent, sz;
    explicit DSU(int n) : parent(static_cast<std::size_t>(n)), sz(static_cast<std::size_t>(n), 1) {
        for (int i = 0; i < n; ++i) { parent[static_cast<std::size_t>(i)] = i; }
    }
    int find(int x) {
        if (parent[static_cast<std::size_t>(x)] != x) {
            parent[static_cast<std::size_t>(x)] = find(parent[static_cast<std::size_t>(x)]);
        }
        return parent[static_cast<std::size_t>(x)];
    }
    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) { return; }
        if (sz[static_cast<std::size_t>(ra)] < sz[static_cast<std::size_t>(rb)]) {
            std::swap(ra, rb);
        }
        parent[static_cast<std::size_t>(rb)] = ra;
        sz[static_cast<std::size_t>(ra)] += sz[static_cast<std::size_t>(rb)];
    }
};

int main() {
    int n{}, m{};
    std::cin >> n >> m;
    DSU dsu(n);
    for (int i = 0; i < m; ++i) {
        int u{}, v{};
        std::cin >> u >> v;
        dsu.unite(u, v);
    }
    int groups = 0;
    for (int i = 0; i < n; ++i) {
        if (dsu.find(i) == i) { ++groups; }
    }
    std::cout << "groups=" << groups << '\n';
    int a{}, b{};
    std::cin >> a >> b;
    std::cout << (dsu.find(a) == dsu.find(b) ? "yes" : "no") << '\n';
    return 0;
}

解析　统计集合个数时不要数 parent[i] == i 而不做路径压缩——必须先 find(i) 把路径压平再比较，否则中间节点会被漏算。