2026-07-19增量偶权环查询。用go语言有一个包含 n 个节点的无向图节点编号从 0 到 n-1初始时图中不存在任何边。现在给定一个边序列 edges其中每个元素都表示一条边包含两个端点和一个权重权重的取值只能是 0 或 1。你需要按照这个序列的顺序逐条处理边对于当前这条边判断如果将其加入当前图中是否会导致出现某个环的边权重之和为奇数。只有当所有环的边权和都是偶数时才真正把这条边加入图中否则就忽略它。最终统计并返回按照此规则成功添加到图中的边的总数。3 n 50000。1 edges.length 50000。edges[i] [ui, vi, wi]。0 ui vi n。所有边都是唯一的。wi 0 或 wi 1。输入 n 3, edges [[0,1,1],[1,2,1],[0,2,1]]。输出 2。解释[0, 1, 1]添加节点 0 和节点 1 之间的边权重为 1。[1, 2, 1]添加节点 1 和节点 2 之间的边权重为 1。[0, 2, 1]节点 0 和节点 2 之间的边图中的虚线不被添加因为环 0 - 1 - 2 - 0 的边权和为 1 1 1 3奇数。题目来自力扣3887。大体步骤如下步骤 1问题转化与数据结构初始化转化判定条件边权为 0 或 1因此一个环的边权和为偶数 (\Longleftrightarrow) 环上所有边权的异或和为 0。如果图中所有环的异或和都为 0那么图中任意两个节点之间的任意路径的异或和都是唯一确定的与路径无关。这个性质正是我们维护的目标。设计并查集使用一个带权并查集包含两个长度为 (n) 的数组fa[x]节点 (x) 的父节点初始时每个节点的父节点都是自己。dis[x]从节点 (x) 到其父节点fa[x]的路径上的边权异或和。初始时所有dis[x] 0。当并查集中一棵树被维护好时对任意节点 (x)我们可以通过不断向上查找根同时累积dis值得到 (x) 到整棵树根节点的异或距离。步骤 2定义带路径压缩的find操作递归查找根节点对于节点 (x)如果fa[x] ! x说明它不是根先递归地找到fa[x]的根节点root。更新异或距离路径压缩在递归返回时已知fa[x]到root的异或距离已经更新好即dis[fa[x]]表示fa[x]到root的异或和。我们希望把 (x) 直接连到root上那么新的dis[x]应该是 (x) 到旧父节点fa[x]的异或和再异或上fa[x]到root的异或和。因此执行dis[x] dis[x] ^ dis[fa[x]]然后将fa[x]设为root。返回根节点返回root。这样经过find(x)后fa[x]直接指向根且dis[x]成为 (x) 到根的异或距离。步骤 3定义merge操作以处理一条边输入一条边(from, to, value)其中value是边权0 或 1。我们要判断这条边能否加入。查找两端所在根及异或距离令x find(from)y find(to)。此时dis[from]是from到根x的异或距离。dis[to]是to到根y的异或距离。情况 A两端已在同一连通块x y此时from与to之间已存在一条路径该路径的异或和为dis[from] ^ dis[to]。如果加入当前边会形成一个新环环的异或和为(dis[from] ^ dis[to]) ^ value要使得环的边权和为偶数必须满足异或和为 0即dis[from] ^ dis[to] value若相等说明加入后不会产生奇权环接受该边返回true但图结构不变因为已经在同一连通块中无需再连边。若不等说明会产生奇权环拒绝该边返回false不修改图。情况 B两端不在同一连通块x ! y此时加入这条边不会形成任何环因为原本不连通所以一定满足“所有环边权和为偶数”的条件我们接受该边并需要将两棵树合并。合并时我们要为新的连接关系设置dis值使得从from到to的异或距离等于value。设我们要将根x接到根y上即设置fa[x] y。那么需要确定dis[x]从x到y的边权异或值使得路径from → x → y → to的总异或和等于value。这个路径的异或和为dis[from] ^ dis[x] ^ dis[to]。令其等于valuedis[from] ^ dis[x] ^ dis[to] value解得dis[x] value ^ dis[from] ^ dis[to]。执行赋值完成合并返回true。步骤 4主流程依次处理所有边初始化并查集ans 0。遍历边列表edges对每条边调用merge(from, to, weight)。如果merge返回true则ans加一。遍历结束后ans即为成功添加到图中的边的总数。步骤 5示例验证n3, edges[[0,1,1],[1,2,1],[0,2,1]]初始节点 0,1,2 各自独立。边 [0,1,1]find(0)0, find(1)1不同根合并。dis[0] 1 ^ 0 ^ 0 1fa[0]1。加入成功ans1。边 [1,2,1]find(1)1, find(2)2不同根合并。dis[1] 1 ^ 0 ^ 0 1fa[1]2。此时dis[0]经过find压缩后会是dis[0]^dis[1]1^10即 0 到根 2 的异或距离为 0。加入成功ans2。边 [0,2,1]find(0)2, dis[0]0find(2)2, dis[2]0。同根检查dis[0] ^ dis[2] 0是否等于 10 ! 1产生奇权环拒绝。最终ans2。复杂度分析时间复杂度并查集使用了路径压缩find和merge操作的均摊时间复杂度几乎是常数级别精确地说是反阿克曼函数 (O(\alpha(n)))。主循环处理 (m) 条边每条边执行常数次find和简单运算因此总时间复杂度为 (O(m \cdot \alpha(n)))。在数据范围内(n, m \leq 50000)这非常高效。额外空间复杂度除了输入和少量变量外我们维护了两个大小为 (n) 的数组fa和dis所以额外空间复杂度为 (O(n))。Go完整代码如下packagemainimport(fmt)typeunionFindstruct{fa[]int// fa[x] 是 x 的代表元dis[]int// dis[x] 从 x 到 fa[x] 的路径异或和}funcnewUnionFind(nint)unionFind{fa:make([]int,n)dis:make([]int,n)fori:rangefa{fa[i]i}returnunionFind{fa,dis}}func(u unionFind)find(xint)int{ifu.fa[x]!x{root:u.find(u.fa[x])u.dis[x]^u.dis[u.fa[x]]u.fa[x]root}returnu.fa[x]}func(u unionFind)merge(from,to,valueint)bool{x,y:u.find(from),u.find(to)ifxy{returnu.dis[from]^u.dis[to]value}u.dis[x]value^u.dis[to]^u.dis[from]u.fa[x]yreturntrue}funcnumberOfEdgesAdded(nint,edges[][]int)(ansint){uf:newUnionFind(n)for_,e:rangeedges{ifuf.merge(e[0],e[1],e[2]){ans}}return}funcmain(){n:3edges:[][]int{{0,1,1},{1,2,1},{0,2,1}}result:numberOfEdgesAdded(n,edges)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-classUnionFind:def__init__(self,n:int):self.falist(range(n))# 父节点代表元self.dis[0]*n# 到父节点的路径异或和deffind(self,x:int)-int:ifself.fa[x]!x:rootself.find(self.fa[x])self.dis[x]^self.dis[self.fa[x]]self.fa[x]rootreturnself.fa[x]defmerge(self,u:int,v:int,w:int)-bool: 尝试加入权重为 w 的边 (u, v)。 若不会产生奇数环即异或条件满足则真正合并并返回 True 否则返回 False。 x,yself.find(u),self.find(v)ifxy:# 已连通检查当前路径异或和是否等于 wreturnself.dis[u]^self.dis[v]w# 未连通合并两个集合self.dis[x]w^self.dis[u]^self.dis[v]self.fa[x]yreturnTruedefnumberOfEdgesAdded(n:int,edges:list[list[int]])-int:ufUnionFind(n)ans0foru,v,winedges:ifuf.merge(u,v,w):ans1returnansif__name____main__:n3edges[[0,1,1],[1,2,1],[0,2,1]]print(numberOfEdgesAdded(n,edges))C完整代码如下#includeiostream#includevectorusingnamespacestd;classUnionFind{public:vectorintfa;// 父节点代表元vectorintdis;// 到父节点的路径异或和UnionFind(intn):fa(n),dis(n,0){for(inti0;in;i){fa[i]i;}}intfind(intx){if(fa[x]!x){introotfind(fa[x]);dis[x]^dis[fa[x]];fa[x]root;}returnfa[x];}// 尝试加入权值为 w 的边 (u, v)// 返回 true 表示加入后无矛盾false 表示会产生奇数环矛盾boolmerge(intu,intv,intw){intxfind(u),yfind(v);if(xy){// 已连通检查当前路径异或和是否等于 wreturn(dis[u]^dis[v])w;}// 未连通合并两个集合fa[x]y;dis[x]w^dis[u]^dis[v];returntrue;}};intnumberOfEdgesAdded(intn,constvectorvectorintedges){UnionFinduf(n);intans0;for(constautoe:edges){if(uf.merge(e[0],e[1],e[2])){ans;}}returnans;}intmain(){intn3;vectorvectorintedges{{0,1,1},{1,2,1},{0,2,1}};intresultnumberOfEdgesAdded(n,edges);coutresultendl;return0;}
