Codechef GALACTIK问题Union-Find解法未AC，求错误原因

我来帮你梳理下代码里的问题，先从你的解题思路和代码实现的偏差说起：

你的解题逻辑回顾 #

• 找出每个连通分量中的最小有效代价（将负代价替换为极大值INT）
• 取所有分量最小代价的全局最小值，用它连接其余所有分量
• 若图已连通则输出0，若存在无有效节点的分量（即分量最小代价为INT）则输出-1

你的代码实现 #

#include<bits/stdc++.h> 
using namespace std; 
typedef long long int ll; 
#define INT 100000000 
unordered_map<ll, ll> parent; 
unordered_map<ll, ll> depth; 
std::vector<ll> cost; 

ll find_set(ll x) { 
    if (x == parent[x])return x; 
    parent[x] = find_set(parent[x]); 
    return parent[x]; 
} 

void union_set(ll x, ll y) { 
    /* Creating a disjoint set such that the node with smallest cost being the root using union-rank concept. */ 
    ll rep1 = find_set(x), rep2 = find_set(y); 
    if (depth[rep1] > depth[rep2])parent[rep1] = rep2; 
    else if (depth[rep2] >= depth[rep1])parent[rep2] = rep1; 
} 

int main() { 
    ll n, m; 
    cin >> n >> m; 
    ll c[m + 1][3]; 
    for (ll i = 1; i <= m; i++) { 
        cin >> c[i][1] >> c[i][2]; //Accepting the edges 
    } 
    for (ll i = 1; i <= n; i++) { 
        parent[i] = i; 
        cin >> depth[i]; 
        if (depth[i] < 0)depth[i] = INT; 
        /*we assume that each negative cost is replaced by a very large positive cost.*/ 
    } 
    for (ll i = 1; i <= m; i++) { 
        union_set(c[i][1], c[i][2]); 
    } 
    set<ll> s; 
    std::vector<ll> v; 
    //storing representatives of each connected component 
    for (auto i = 1; i <= n; i++)s.insert(depth[find_set(i)]); 
    for (auto it = s.begin(); it != s.end(); it++)v.push_back(*it); 
    sort(v.begin(), v.end()); 
    if (s.size() == 1) { 
        //Graph is connected if there is only 1 connected comp 
        cout << 0 << endl; 
        return 0; 
    } 
    bool flag = false; 
    ll p = 0; 
    for (ll i = 1; i < v.size(); i++) { 
        if (v[i] == INT) { 
            flag = true; 
            break; 
        } 
        p += (v[0]+v[i]); 
    } 
    if (flag)cout << -1 << endl; 
    else cout << p << endl; 
    return 0; 
}

代码中的核心错误分析 #

1. 变量命名混淆逻辑 #

你把存储节点代价的变量命名为depth，但depth在并查集里通常用来表示树的深度（用于按秩合并），这直接导致你在合并逻辑里完全搞错了比较对象——你本来应该比较节点的代价，却错误地把这个变量当成树的深度来处理，偏离了让「代价最小的节点作为根」的初衷。

2. 并查集的合并逻辑完全错误 #

你的注释说要让代价最小的节点作为根，但实际代码的逻辑完全相反：

• 当前代码中if (depth[rep1] > depth[rep2])parent[rep1] = rep2;的逻辑是：如果rep1的代价更大，就把rep1的父节点设为rep2？这看起来是对的，但你后续的else if (depth[rep2] >= depth[rep1])parent[rep2] = rep1;会把rep2的父节点设为rep1，这会直接覆盖之前的正确操作，导致合并逻辑彻底混乱。
• 正确的合并逻辑应该是：比较两个根的代价，把代价更大的根的父节点指向代价更小的根；如果代价相同，可以用真正的rank数组（记录树的深度）来做按秩合并，保持树的平衡。

3. 收集连通分量最小代价的方式错误 #

你现在的做法是把每个节点根对应的depth（代价）插入到set中，但因为你的合并逻辑没有保证根节点是分量中代价最小的节点，所以根节点的代价不一定是该分量的最小代价，这导致你收集到的不是每个分量的真实最小代价。

4. 极端情况处理遗漏 #

比如当所有分量的最小代价都是INT时，你的代码会输出-1，但如果只有一个这样的分量，且图已经连通，应该输出0吗？不，这种情况应该输出-1，因为这个分量没有有效节点，但你的当前逻辑在s.size()==1时直接输出0，没有判断这个唯一的分量是否是无效的。

修正建议 #

1. 修正变量命名：把depth改成cost，新增rank数组用于并查集的按秩合并。
2. 修复合并逻辑：合并时优先让代价小的节点作为根，代价相同时用按秩合并优化树结构。
3. 正确收集分量最小代价：遍历所有节点，用哈希表记录每个根对应的分量最小代价。
4. 完善极端情况判断：在判断图连通时，额外检查该分量是否是无效的（代价为INT）。

举个修正后的核心代码片段：

unordered_map<ll, ll> parent; 
unordered_map<ll, ll> cost; 
unordered_map<ll, ll> rank; // 真正的按秩合并深度

ll find_set(ll x) { 
    if (x == parent[x]) return x; 
    return parent[x] = find_set(parent[x]); // 路径压缩
} 

void union_set(ll x, ll y) { 
    ll rep1 = find_set(x), rep2 = find_set(y); 
    if (rep1 == rep2) return;
    // 让代价小的作为根
    if (cost[rep1] < cost[rep2]) {
        parent[rep2] = rep1;
        if (rank[rep1] == rank[rep2]) rank[rep1]++;
    } else {
        parent[rep1] = rep2;
        if (rank[rep2] == rank[rep1]) rank[rep2]++;
    }
}

收集分量最小代价的部分：

unordered_map<ll, ll> root_min;
for (ll i = 1; i <= n; i++) {
    ll root = find_set(i);
    if (root_min.find(root) == root_min.end()) {
        root_min[root] = cost[i];
    } else {
        root_min[root] = min(root_min[root], cost[i]);
    }
}

vector<ll> v;
bool has_invalid = false;
ll total = 0, global_min = INT_MAX;
for (auto& [root, min_c] : root_min) {
    if (min_c == INT) {
        has_invalid = true;
        break;
    }
    v.push_back(min_c);
    global_min = min(global_min, min_c);
}

if (has_invalid) {
    cout << -1 << endl;
} else if (v.size() == 1) {
    cout << 0 << endl;
} else {
    ll sum = 0;
    for (ll c : v) sum += c;
    total = sum + global_min * (v.size() - 2);
    cout << total << endl;
}

内容的提问来源于stack exchange，提问作者Chetanrns