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：问题转化与数据结构初始化

1. 转化判定条件
   边权为 0 或 1，因此一个环的边权和为偶数 (\Longleftrightarrow) 环上所有边权的异或和为 0。
   如果图中所有环的异或和都为 0，那么图中任意两个节点之间的任意路径的异或和都是唯一确定的（与路径无关）。这个性质正是我们维护的目标。

2. 设计并查集
   使用一个带权并查集，包含两个长度为 (n) 的数组：

   • fa[x]：节点 (x) 的父节点，初始时每个节点的父节点都是自己。
   • dis[x]：从节点 (x) 到其父节点fa[x]的路径上的边权异或和。初始时所有dis[x] = 0。

   当并查集中一棵树被维护好时，对任意节点 (x)，我们可以通过不断向上查找根，同时累积dis值，得到 (x) 到整棵树根节点的异或距离。

步骤 2：定义带路径压缩的find操作

1. 递归查找根节点
   对于节点 (x)，如果fa[x] != x，说明它不是根，先递归地找到fa[x]的根节点root。

2. 更新异或距离（路径压缩）
   在递归返回时，已知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。

3. 返回根节点
   返回root。这样，经过find(x)后，fa[x]直接指向根，且dis[x]成为 (x) 到根的异或距离。

步骤 3：定义merge操作以处理一条边

输入一条边(from, to, value)，其中value是边权（0 或 1）。我们要判断这条边能否加入。

1. 查找两端所在根及异或距离
   令x = find(from)，y = find(to)。此时：

   • dis[from]是from到根x的异或距离。
   • dis[to]是to到根y的异或距离。

2. 情况 A：两端已在同一连通块（x == y）
   此时from与to之间已存在一条路径，该路径的异或和为dis[from] ^ dis[to]。
   如果加入当前边，会形成一个新环，环的异或和为：
   (dis[from] ^ dis[to]) ^ value
   要使得环的边权和为偶数，必须满足异或和为 0，即
   dis[from] ^ dis[to] == value

   • 若相等，说明加入后不会产生奇权环，接受该边，返回true（但图结构不变，因为已经在同一连通块中，无需再连边）。
   • 若不等，说明会产生奇权环，拒绝该边，返回false，不修改图。

3. 情况 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]。
   令其等于value：
   dis[from] ^ dis[x] ^ dis[to] = value
   解得dis[x] = value ^ dis[from] ^ dis[to]。
   执行赋值，完成合并，返回true。

步骤 4：主流程：依次处理所有边

1. 初始化并查集，ans = 0。
2. 遍历边列表edges，对每条边调用merge(from, to, weight)。
3. 如果merge返回true，则ans加一。
4. 遍历结束后，ans即为成功添加到图中的边的总数。

步骤 5：示例验证（n=3, 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 = 1，fa[0]=1。加入成功，ans=1。
• 边 [1,2,1]：find(1)=1, find(2)=2，不同根，合并。dis[1] = 1 ^ 0 ^ 0 = 1，fa[1]=2。此时dis[0]经过find压缩后会是dis[0]^dis[1]=1^1=0，即 0 到根 2 的异或距离为 0。加入成功，ans=2。
• 边 [0,2,1]：find(0)=2, dis[0]=0；find(2)=2, dis[2]=0。同根，检查dis[0] ^ dis[2] = 0是否等于 1？0 != 1，产生奇权环，拒绝。最终ans=2。

复杂度分析

• 时间复杂度
  并查集使用了路径压缩，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)ifx==y{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.fa=list(range(n))# 父节点（代表元）self.dis=[0]*n# 到父节点的路径异或和deffind(self,x:int)->int:ifself.fa[x]!=x:root=self.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,y=self.find(u),self.find(v)ifx==y:# 已连通：检查当前路径异或和是否等于 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:uf=UnionFind(n)ans=0foru,v,winedges:ifuf.merge(u,v,w):ans+=1returnansif__name__=="__main__":n=3edges=[[0,1,1],[1,2,1],[0,2,1]]print(numberOfEdgesAdded(n,edges))

C++完整代码如下：

#include<iostream>#include<vector>usingnamespacestd;classUnionFind{public:vector<int>fa;// 父节点（代表元）vector<int>dis;// 到父节点的路径异或和UnionFind(intn):fa(n),dis(n,0){for(inti=0;i<n;++i){fa[i]=i;}}intfind(intx){if(fa[x]!=x){introot=find(fa[x]);dis[x]^=dis[fa[x]];fa[x]=root;}returnfa[x];}// 尝试加入权值为 w 的边 (u, v)// 返回 true 表示加入后无矛盾，false 表示会产生奇数环（矛盾）boolmerge(intu,intv,intw){intx=find(u),y=find(v);if(x==y){// 已连通，检查当前路径异或和是否等于 wreturn(dis[u]^dis[v])==w;}// 未连通，合并两个集合fa[x]=y;dis[x]=w^dis[u]^dis[v];returntrue;}};intnumberOfEdgesAdded(intn,constvector<vector<int>>&edges){UnionFinduf(n);intans=0;for(constauto&e:edges){if(uf.merge(e[0],e[1],e[2])){++ans;}}returnans;}intmain(){intn=3;vector<vector<int>>edges={{0,1,1},{1,2,1},{0,2,1}};intresult=numberOfEdgesAdded(n,edges);cout<<result<<endl;return0;}