说明

该代码解决的问题是：在一个由多个立方体领土组成的帝国中，随着君主制国家逐月分裂出去，计算剩余帝国领土变得不连通的月份数量。每个君主制国家由多个连通的领土组成，分裂顺序会影响剩余领土的连通性。

算法标签

• 并查集（Union-Find）
• 连通分量分析
• 三维网格处理

解题思路

1. 问题建模：将帝国领土建模为一个三维网格（高度 k，深度 m，宽度 n），每个领土是一个立方体，编号为 h * (n * m) + d * n + w。
2. 分裂过程模拟：按照分裂的逆序（从最后一个月到第一个月）逐步添加领土到剩余帝国中，使用并查集维护连通性。
3. 连通性检查：每次添加领土后，检查剩余帝国的连通分量数量。如果连通分量多于1，则当前月份会导致帝国不连通。
4. 结果统计：统计所有导致剩余帝国不连通的月份数量。

分析

1. 输入处理：读取每个君主制国家的领土列表，并按分裂的逆序处理（因为分裂是逐月移除领土，而逆序处理相当于逐步添加领土）。
2. 并查集维护：使用并查集数据结构动态维护剩余领土的连通性。每次添加领土时，检查其六个方向的相邻领土，合并连通分量。
3. 连通分量计数：每次添加领土后，统计剩余领土的连通分量数量。如果数量大于1，则当前月份会导致帝国不连通。
4. 资源管理：动态分配和释放并查集节点的内存，避免内存泄漏。

实现步骤

1. 初始化：
   • 读取输入数据，包括帝国尺寸 n, m, k 和分裂的君主制国家数量 l。
   • 存储每个君主制国家的领土列表。
2. 逆序处理分裂：
   • 从最后一个分裂的君主制国家开始，逐步将领土添加到剩余帝国中。
   • 使用三维数组 exists 标记领土是否存在，node_map 存储并查集节点。
3. 并查集操作：
   • 添加领土时，创建并查集节点，检查六个方向的相邻领土，合并连通分量。
   • 动态更新连通分量数量 count。
4. 连通性检查：
   • 在每次添加领土后（除第一个月外），检查连通分量数量 count。如果 count > 1，则当前月份会导致帝国不连通，增加结果计数 res。
5. 输出结果：
   • 对每个测试用例，输出导致帝国不连通的月份数量。
6. 资源释放：
   • 释放动态分配的并查集节点内存。

代码注释

• Node 结构体：实现并查集的路径压缩和按秩合并。
• 主循环：
  • 读取输入并初始化数据结构。
  • 逆序处理君主制国家，动态维护连通性。
  • 检查并统计不连通的月份。
• 内存管理：确保并查集节点内存被正确释放。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

struct Node {
    Node* parent;
    int rank;

    Node() : parent(this), rank(0) {}

    Node* findSet() {
        if (parent != this) {
            parent = parent->findSet();
        }
        return parent;
    }

    void link(Node* other) {
        if (rank > other->rank) {
            other->parent = this;
        } else {
            parent = other;
            if (rank == other->rank) {
                other->rank++;
            }
        }
    }

    void unionWith(Node* other) {
        findSet()->link(other->findSet());
    }
};

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        int n, m, k, l;
        cin >> n >> m >> k >> l;
        cin.ignore();

        vector<vector<int>> monarchies;
        for (int i = 0; i < l; ++i) {
            string line;
            getline(cin, line);
            istringstream iss(line);
            int p;
            iss >> p;
            vector<int> dominions;
            int dominion;
            while (iss >> dominion) {
                dominions.push_back(dominion);
            }
            monarchies.push_back(dominions);
        }

        vector<vector<vector<bool>>> exists(k, vector<vector<bool>>(m, vector<bool>(n, false)));
        vector<vector<vector<Node*>>> node_map(k, vector<vector<Node*>>(m, vector<Node*>(n, nullptr)));
        int count = 0;
        int res = 0;

        for (int step = 0; step < l; ++step) {
            const vector<int>& dominions = monarchies[l - 1 - step];
            for (int dom : dominions) {
                int h = dom / (n * m);
                int remaining = dom % (n * m);
                int d = remaining / n;
                int w = remaining % n;

                if (!exists[h][d][w]) {
                    exists[h][d][w] = true;
                    Node* node = new Node();
                    node_map[h][d][w] = node;
                    count++;

                    const int dirs[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
                    for (const auto& dir : dirs) {
                        int nh = h + dir[0];
                        int nd = d + dir[1];
                        int nw = w + dir[2];
                        if (nh >= 0 && nh < k && nd >= 0 && nd < m && nw >= 0 && nw < n) {
                            if (exists[nh][nd][nw]) {
                                Node* neighbor = node_map[nh][nd][nw];
                                Node* root1 = node->findSet();
                                Node* root2 = neighbor->findSet();
                                if (root1 != root2) {
                                    root1->unionWith(root2);
                                    count--;
                                }
                            }
                        }
                    }
                }
            }

            int current_i = l - step - 1;
            if (current_i >= 1) {
                if (count > 1) {
                    res++;
                }
            }
        }

        for (int h = 0; h < k; ++h) {
            for (int d = 0; d < m; ++d) {
                for (int w = 0; w < n; ++w) {
                    if (node_map[h][d][w] != nullptr) {
                        delete node_map[h][d][w];
                    }
                }
            }
        }

        cout << res << endl;
    }
    return 0;
}