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

福大大架构师每日一题

发布于 2026-07-21 13:29:02

410

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

#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
public:
    vector<int> fa;   // 父节点（代表元）
    vector<int> 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<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<vector<int>> edges = {{0, 1, 1}, {1, 2, 1}, {0, 2, 1}};
    int result = numberOfEdgesAdded(n, edges);
    cout << result << endl;
    return0;
}