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) 的数组：当并查集中一棵树被维护好时，对任意节点 (x)，我们可以通过不断向上查找根，同时累积
dis值，得到 (x) 到整棵树根节点的异或距离。
•
fa[x]：节点 (x) 的父节点，初始时每个节点的父节点都是自己。•
dis[x]：从节点 (x) 到其父节点fa[x]的路径上的边权异或和。初始时所有dis[x] = 0。
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) 到根的异或距离。
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即为成功添加到图中的边的总数。
• 初始：节点 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))。
package main
import (
"fmt"
)
type unionFind struct {
fa []int// fa[x] 是 x 的代表元
dis []int// dis[x] = 从 x 到 fa[x] 的路径异或和
}
func newUnionFind(n int) unionFind {
fa := make([]int, n)
dis := make([]int, n)
for i := range fa {
fa[i] = i
}
return unionFind{fa, dis}
}
func (u unionFind) find(x int) int {
if u.fa[x] != x {
root := u.find(u.fa[x])
u.dis[x] ^= u.dis[u.fa[x]]
u.fa[x] = root
}
return u.fa[x]
}
func (u unionFind) merge(from, to, value int) bool {
x, y := u.find(from), u.find(to)
if x == y {
return u.dis[from]^u.dis[to] == value
}
u.dis[x] = value ^ u.dis[to] ^ u.dis[from]
u.fa[x] = y
returntrue
}
func numberOfEdgesAdded(n int, edges [][]int) (ans int) {
uf := newUnionFind(n)
for _, e := range edges {
if uf.merge(e[0], e[1], e[2]) {
ans++
}
}
return
}func main() {
n := 3
edges := [][]int{{0, 1, 1}, {1, 2, 1}, {0, 2, 1}}
result := numberOfEdgesAdded(n, edges)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
class UnionFind:
def __init__(self, n: int):
self.fa = list(range(n)) # 父节点（代表元）
self.dis = [0] * n # 到父节点的路径异或和
def find(self, x: int) -> int:
if self.fa[x] != x:
root = self.find(self.fa[x])
self.dis[x] ^= self.dis[self.fa[x]]
self.fa[x] = root
return self.fa[x]
def merge(self, u: int, v: int, w: int) -> bool:
"""
尝试加入权重为 w 的边 (u, v)。
若不会产生奇数环（即异或条件满足）则真正合并并返回 True，
否则返回 False。
"""
x, y = self.find(u), self.find(v)
if x == y:
# 已连通：检查当前路径异或和是否等于 w
return self.dis[u] ^ self.dis[v] == w
# 未连通：合并两个集合
self.dis[x] = w ^ self.dis[u] ^ self.dis[v]
self.fa[x] = y
return True
def numberOfEdgesAdded(n: int, edges: list[list[int]]) -> int:
uf = UnionFind(n)
ans = 0
for u, v, w in edges:
if uf.merge(u, v, w):
ans += 1
return ansif __name__ == "__main__":
n = 3
edges = [[0, 1, 1], [1, 2, 1], [0, 2, 1]]
print(numberOfEdgesAdded(n, edges))
C++完整代码如下：
using namespace std;
class UnionFind {
public:
vector fa; // 父节点（代表元）
vector dis; // 到父节点的路径异或和
UnionFind(int n) : fa(n), dis(n, 0) {
for (int i = 0; i < n; ++i) {
fa[i] = i;
}
}
int find(int x) {
if (fa[x] != x) {
int root = find(fa[x]);
dis[x] ^= dis[fa[x]];
fa[x] = root;
}
return fa[x];
}
// 尝试加入权值为 w 的边 (u, v)
// 返回 true 表示加入后无矛盾，false 表示会产生奇数环（矛盾）
bool merge(int u, int v, int w) {
int x = find(u), y = find(v);
if (x == y) {
// 已连通，检查当前路径异或和是否等于 w
return (dis[u] ^ dis[v]) == w;
}
// 未连通，合并两个集合
fa[x] = y;
dis[x] = w ^ dis[u] ^ dis[v];
returntrue;
}
};int numberOfEdgesAdded(int n, const vector int >>& edges) {
UnionFind uf(n);
int ans = 0 ;
for ( const auto& e : edges) {
if (uf.merge(e[ 0 ], e[ 1 ], e[ 2 ])) {
++ans;
}
}
return ans;
}
int main() {
int n = 3 ;
vector int >> edges = {{ 0 , 1 , 1 }, { 1 , 2 , 1 }, { 0 , 2 , 1 }};
int result = numberOfEdgesAdded(n, edges);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴