2026-07-19：增量偶权环查询。用go语言，有一个包含 n 个节点的无向图，节点编号从 0 到 n-1，初始时图中不存在任何边。现在给定一个边序

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。

步骤 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完整代码如下：

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 ans

 if __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助力您的未来发展。