Hard

题目描述

给定一个正整数 n。

有一个无向图，包含 n 个节点，标号从 0 到 n - 1。初始时，图中没有边。

还给定一个二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间的一条权重为 wi 的边。权重 wi 只能是 0 或 1。

按照 edges 中给定的顺序处理边。对于每条边，只有在将其添加到图中后，生成图中每个环的边权重之和都是偶数时，才将该边添加到图中。

返回成功添加到图中的边数。

示例 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，是奇数。

示例 2：

输入：n = 3, edges = [[0,1,1],[1,2,1],[0,2,0]]
输出：3
解释：
- [0, 1, 1]：在顶点 0 和顶点 1 之间添加权重为 1 的边。
- [1, 2, 1]：在顶点 1 和顶点 2 之间添加权重为 1 的边。
- [0, 2, 0]：添加顶点 0 和顶点 2 之间权重为 0 的边。
  注意环 0-1-2-0 的总边权重为 1+1+0=2，是偶数。

约束条件：

  • 3 <= n <= 5 * 10^4
  • 1 <= edges.length <= 5 * 10^4
  • edges[i] = [ui, vi, wi]
  • 0 <= ui < vi < n
  • 所有边都不相同
  • wi = 0 或 wi = 1

解题思路

这道题的关键在于理解环权重和的奇偶性约束。我们可以将问题转化为二分图着色问题。

核心思想：

  1. 给每个节点分配一个位值（0或1）
  2. 权重为0的边连接相同位值的节点
  3. 权重为1的边连接不同位值的节点
  4. 如果满足这个约束，任何环的权重和都是偶数

具体分析：

  • 对于权重为0的边(u,v)：要求bit[u] = bit[v]
  • 对于权重为1的边(u,v)：要求bit[u] ≠ bit[v]

使用并查集来维护连通性和相对奇偶性：

  • 每个节点维护相对于其根节点的奇偶性关系
  • 当添加新边时，检查是否与已有约束冲突
  • 如果两个节点已连通，检查它们的相对关系是否与边权重一致
  • 如果不连通，合并两个连通分量

算法流程：

  1. 初始化并查集，每个节点的相对奇偶性为0
  2. 对每条边，找到两端点的根节点
  3. 如果根节点相同（已连通），检查相对奇偶性是否与边权重匹配
  4. 如果根节点不同（未连通），根据边权重合并连通分量
  5. 只有不产生冲突的边才被添加

代码实现

class Solution {
public:
    vector<int> parent, parity;
    
    int find(int x) {
        if (parent[x] != x) {
            int old_parent = parent[x];
            parent[x] = find(old_parent);
            parity[x] ^= parity[old_parent];
        }
        return parent[x];
    }
    
    int numberOfEdgesAdded(int n, vector<vector<int>>& edges) {
        parent.resize(n);
        parity.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            parity[i] = 0;
        }
        
        int count = 0;
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int root_u = find(u), root_v = find(v);
            
            if (root_u == root_v) {
                // Already connected, check if parity matches
                if ((parity[u] ^ parity[v]) == w) {
                    count++;
                }
            } else {
                // Not connected, merge components
                parent[root_v] = root_u;
                parity[root_v] = parity[u] ^ parity[v] ^ w;
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def numberOfEdgesAdded(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        parity = [0] * n
        
        def find(x):
            if parent[x] != x:
                old_parent = parent[x]
                parent[x] = find(old_parent)
                parity[x] ^= parity[old_parent]
            return parent[x]
        
        count = 0
        for u, v, w in edges:
            root_u = find(u)
            root_v = find(v)
            
            if root_u == root_v:
                # Already connected, check if parity matches
                if (parity[u] ^ parity[v]) == w:
                    count += 1
            else:
                # Not connected, merge components
                parent[root_v] = root_u
                parity[root_v] = parity[u] ^ parity[v] ^ w
                count += 1
        
        return count

public class Solution {
    private int[] parent, parity;
    
    private int Find(int x) {
        if (parent[x] != x) {
            int oldParent = parent[x];
            parent[x] = Find(oldParent);
            parity[x] ^= parity[oldParent];
        }
        return parent[x];
    }
    
    public int NumberOfEdgesAdded(int n, int[][] edges) {
        parent = new int[n];
        parity = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            parity[i] = 0;
        }
        
        int count = 0;
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int rootU = Find(u), rootV = Find(v);
            
            if (rootU == rootV) {
                // Already connected, check if parity matches
                if ((parity[u] ^ parity[v]) == w) {
                    count++;
                }
            } else {
                // Not connected, merge components
                parent[rootV] = rootU;
                parity[rootV] = parity[u] ^ parity[v] ^ w;
                count++;
            }
        }
        return count;
    }
}

var numberOfEdgesAdded = function(n, edges) {
    const parent = Array(n).fill(0).map((_, i) => i);
    const parity = Array(n).fill(0);
    
    function find(x) {
        if (parent[x] !== x) {
            const root = find(parent[x]);
            parity[x] ^= parity[parent[x]];
            parent[x] = root;
        }
        return parent[x];
    }
    
    let count = 0;
    
    for (const [u, v, w] of edges) {
        const rootU = find(u);
        const rootV = find(v);
        
        if (rootU !== rootV) {
            parent[rootV] = rootU;
            parity[rootV] = parity[u] ^ parity[v] ^ w;
            count++;
        } else {
            const cycleWeight = parity[u] ^ parity[v] ^ w;
            if (cycleWeight === 0) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度值说明
时间复杂度O(E·α(N))E为边数，α为阿克曼函数的反函数，几乎为常数
空间复杂度O(N)存储并查集的parent和parity数组