千问 LeetCode 3887. 增量偶权环查询 C++实现

这道题的核心是带权并查集，将"环边权和为偶数"转化为"环上边权异或和为 0"，通过维护每个节点到根的异或距离来判断新边是否会形成奇权环。

核心思路

1. 问题转化：边权为 0 或 1，环的边权和为偶数 ⟺ 环上所有边权的异或和为 0
2. 维护目标：如果图中所有环的异或和都为 0，那么任意两点间任意路径的异或和都是唯一确定的（与路径无关）
3. 带权并查集：用 fa[x] 记录父节点，dis[x] 记录 x 到父节点路径上的边权异或和。通过路径压缩，find(x) 后 dis[x] 就是 x 到根的异或距离
4. 判断逻辑：对于边 (u, v, w)，若 u、v 已在同一集合，检查 dis[u] ^ dis[v] ^ w 是否为 0；为 0 说明新环异或和为偶数，可加入；否则会产生奇权环，跳过

C++ 实现

class Solution {
vector<int> fa, dis; // dis[x]: x 到 fa[x] 路径上的边权异或和

// 带路径压缩的 find，调用后 dis[x] 变为 x 到根的异或距离
int find(int x) {
if (fa[x] != x) {
int root = find(fa[x]);
dis[x] ^= dis[fa[x]]; // 累积异或距离
fa[x] = root;
}
return fa[x];
}

public:
int numberOfEdgesAdded(int n, vector<vector<int>>& edges) {
fa.resize(n);
dis.assign(n, 0);
for (int i = 0; i < n; i++) fa[i] = i;

int count = 0;
for (auto& edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
int ru = find(u), rv = find(v);

if (ru == rv) {
// 已在同一集合：检查新环的异或和
// 环的异或和 = dis[u] ^ dis[v] ^ w
if ((dis[u] ^ dis[v] ^ w) == 0) {
count++; // 偶权环，可以加入
}
// 否则产生奇权环，跳过
} else {
// 不在同一集合：合并，不会形成环
// 需要让 dis[u] ^ dis[v] ^ w = 0 成立
// 即 dis[ru] = dis[u] ^ dis[v] ^ w
dis[ru] = dis[u] ^ dis[v] ^ w;
fa[ru] = rv;
count++;
}
}
return count;
}
};

关键点解析

- 路径压缩时的异或更新：dis[x] ^= dis[fa[x]] 是因为 x 到根的异或距离 = x 到旧父节点的异或 ⊕ 旧父节点到根的异或
- 合并时的权重设置：合并 ru 和 rv 时，设置 dis[ru] = dis[u] ^ dis[v] ^ w，保证合并后 u 和 v 之间的异或距离恰好等于 w
- 时间复杂度：O(m · α(n))，其中 m 是边数，α 是反阿克曼函数，近似线性
- 空间复杂度：O(n)

示例验证

以 n=3, edges=[[0,1,1],[1,2,1],[0,2,1]] 为例：

1. 边 (0,1,1)：0 和 1 不在同一集合，合并，count=1
2. 边 (1,2,1)：1 和 2 不在同一集合，合并，count=2
3. 边 (0,2,1)：0 和 2 已在同一集合，环异或和 = dis[0]^dis[2]^1 = 1^1^1 = 1（奇数），跳过

最终返回 2，与预期一致。

需要我帮你整理一份带权并查集（异或/加法）的通用模板吗？遇到类似题可以直接套用。