题目分析与思路提示

1. 数据结构：并查集 (Union-Find)

我们需要维护两个核心数组：

• fa[i] (或 parent[i])：表示节点 $i$ 的父节点。
  • 初始化时，fa[i] = i，表示自己是自己的“老大”。
  • 如果 fa[i] == i，说明 $i$ 是这个集合的根节点 (Root)。
• sz[i] (或 size[i])：表示以 $i$ 为根的集合的大小。
  • 初始化时，sz[i] = 1。
  • 注意：只有根节点的 sz 值是有意义的。

2. 核心操作

• Find (查找根节点)：
  • 沿着 fa 数组一直往上找，直到找到 fa[x] == x 的点。
  • 路径压缩 (Path Compression)：这是优化的关键！在查找的过程中，直接把沿途经过的所有节点的父节点都改为根节点。这样下次再查，一步就能跳到根。
  • 代码：if (x != fa[x]) fa[x] = find(fa[x]); return fa[x];
• Union (合并)：
  • 给出 $u, v$，先找到它们的根 $root_u = \text{find}(u)$, $root_v = \text{find}(v)$。
  • 如果 $root_u == root_v$：说明已经在同一个集合了，这是一次多余的操作。
  • 如果 $root_u \neq root_v$：将其中一个根（例如 $root_v$）挂在另一个根（$root_u$）下面。
    • fa[root_v] = root_u
    • 同时更新大小：sz[root_u] += sz[root_v]
    • 集合总数减 1。

3. 统计逻辑

• redundant_ops：记录多余圣旨数。每次 Union 发现根相同时 +1。
• set_count：记录独立区数量。初始为 $N$，每次成功合并（根不同）时 -1。
• max_size：记录最大区大小。每次成功合并时，用合并后的新大小更新它。初始值为 1。

4. 复杂度分析

• 时间复杂度：使用路径压缩的并查集，单次操作复杂度为 $O(\alpha(N))$，其中 $\alpha$ 是反阿克曼函数，增长极慢，可视为常数 $O(1)$。总复杂度 $O(M \alpha(N)) \approx O(M)$。
• 空间复杂度：$O(N)$，用于存储数组。

参考代码 (C++14)

/**
 * 题目：大秦的统一 (The Unification of Great Qin)
 * 难度：GESP 6级
 * 算法：并查集 (DSU)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 并查集核心数组
int fa[MAXN];   // 父节点
int sz[MAXN];   // 集合大小

// 初始化
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;  // 自己是自己的父节点
        sz[i] = 1;  // 初始每个集合大小为1
    }
}

// 查找函数（带路径压缩）
int find(int x) {
    if (x == fa[x]) {
        return x;
    }
    // 递归查找，并把沿途节点的父节点直接设为根节点
    return fa[x] = find(fa[x]); 
}

// 合并函数
// 返回 true 表示合并成功（原本不在一组）
// 返回 false 表示合并失败（原本就在一组，操作多余）
bool unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY) {
        return false; // 已经在同一个集合
    }

    // 将 rootY 挂在 rootX 下面
    fa[rootY] = rootX;
    
    // 更新 rootX 的大小
    sz[rootX] += sz[rootY];
    
    return true;
}

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    init(N);

    int set_count = N;      // 初始有 N 个独立区
    int max_size = 1;       // 初始最大区大小为 1
    int redundant_ops = 0;  // 多余的圣旨数

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;

        // 尝试合并
        if (unite(u, v)) {
            // 合并成功
            set_count--; 
            
            // 更新最大集合大小
            // 注意：合并后，只有新根节点(这里是 rootX)的 sz 是准确的
            int root = find(u); // 重新找一下根，或者利用 unite 里的逻辑
            if (sz[root] > max_size) {
                max_size = sz[root];
            }
        } else {
            // 合并失败，说明多余
            redundant_ops++;
        }
    }

    cout << set_count << " " << max_size << " " << redundant_ops << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
struct DSU {
    vector<int> fa, sz;
    DSU(int n) {
        fa.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    // 返回是否成功合并
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        fa[ry] = rx;
        sz[rx] += sz[ry];
        return true;
    }
    int get_size(int x) {
        return sz[find(x)];
    }
};

void solve(int N, int M, const vector<pair<int, int>>& ops, ofstream& fout) {
    DSU dsu(N);
    int sets = N;
    int max_sz = 1;
    int redundant = 0;

    for (const auto& op : ops) {
        if (dsu.unite(op.first, op.second)) {
            sets--;
            max_sz = max(max_sz, dsu.get_size(op.first));
        } else {
            redundant++;
        }
    }
    fout << sets << " " << max_sz << " " << redundant << endl;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<pair<int, int>> ops;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; M = 4;
            ops = {{1,2}, {2,3}, {4,5}, {1,3}};
        }
        else if (i == 2) {
            // 样例2 (全连通)
            N = 6; M = 5;
            ops = {{1,2}, {3,4}, {5,6}, {1,3}, {3,5}};
        }
        else if (i == 3) {
            // 零操作
            N = 10; M = 0;
        }
        else if (i == 4) {
            // 链状连接 (1-2, 2-3...)
            N = 100; M = N - 1;
            for(int k=1; k<N; k++) ops.push_back({k, k+1});
        }
        else if (i == 5) {
            // 菊花图连接 (1-2, 1-3...)
            N = 100; M = N - 1;
            for(int k=2; k<=N; k++) ops.push_back({1, k});
        }
        else if (i == 6) {
            // 大量冗余操作 (重复连接相同的点)
            N = 50; M = 200;
            for(int k=0; k<M; k++) ops.push_back({1, 2});
        }
        else if (i == 7) {
            // 完全二分图 (为了制造复杂的连接)
            N = 100; M = 500;
            for(int k=0; k<M; k++) {
                ops.push_back({randRange(1, N/2), randRange(N/2+1, N)});
            }
        }
        else {
            // 大规模随机
            N = 100000;
            if (i == 8) M = N / 2; // 稀疏，可能有很多孤立点
            else if (i == 9) M = N; // 中等
            else M = 200000; // 稠密，大概率连成一大片

            for(int k=0; k<M; k++) {
                int u = randRange(1, N);
                int v = randRange(1, N);
                // 允许 u=v，虽然题目说 u!=v 最好，但并查集能处理
                while(u == v) v = randRange(1, N);
                ops.push_back({u, v});
            }
        }

        // 写入输入
        fin << N << " " << M << endl;
        for (const auto& op : ops) {
            fin << op.first << " " << op.second << "\n";
        }

        // 写入输出
        solve(N, M, ops, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}