千问 LeetCode 3887. 增量偶权环查询 C++实现-北京尧图网络

这道题的核心是带权并查集将环边权和为偶数转化为环上边权异或和为 0通过维护每个节点到根的异或距离来判断新边是否会形成奇权环。核心思路1. 问题转化边权为 0 或 1环的边权和为偶数 ⟺ 环上所有边权的异或和为 02. 维护目标如果图中所有环的异或和都为 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 {vectorint 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, vectorvectorint 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] ^ wif ((dis[u] ^ dis[v] ^ w) 0) {count; // 偶权环可以加入}// 否则产生奇权环跳过} else {// 不在同一集合合并不会形成环// 需要让 dis[u] ^ dis[v] ^ w 0 成立// 即 dis[ru] dis[u] ^ dis[v] ^ wdis[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)示例验证以 n3, edges[[0,1,1],[1,2,1],[0,2,1]] 为例1. 边 (0,1,1)0 和 1 不在同一集合合并count12. 边 (1,2,1)1 和 2 不在同一集合合并count23. 边 (0,2,1)0 和 2 已在同一集合环异或和 dis[0]^dis[2]^1 1^1^1 1奇数跳过最终返回 2与预期一致。需要我帮你整理一份带权并查集异或/加法的通用模板吗遇到类似题可以直接套用。

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

相关推荐

SSH终端的剪切粘贴和移动的区别

Spring Boot多模块项目配置加载难题：从原理到实战解决方案

王虹、邓煜、张益唐、韦东奕四位数学家研究方向预测

更多资讯

链游2.0：构建可持续的区块链游戏经济模型与技术架构

从print大法到线上问题排查：caveman调试法为什么至今仍是有效底牌

AI Agent任务完成微信通知实现方案

基于CANN架构的智能视频分析系统设计与优化

营销技能体系拆解：从执行到操盘手的能力清单

hyperframes参考架构实战：从GPU利用率到分布式训练优化

今日更新

学生选课系统DFD图绘制指南：边界划分与分层校验实战

JIRA敏捷落地：Scrum角色权限、Sprint与燃尽图避坑指南

SEMI S8人机工程验收实战：从条款拆解到现场实测的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？