這道題的核心是帶權并查集將環(huán)邊權和為偶數(shù)轉化為環(huán)上邊權異或和為 0通過維護每個節(jié)點到根的異或距離來判斷新邊是否會形成奇權環(huán)。核心思路1. 問題轉化邊權為 0 或 1環(huán)的邊權和為偶數(shù) ? 環(huán)上所有邊權的異或和為 02. 維護目標如果圖中所有環(huán)的異或和都為 0那么任意兩點間任意路徑的異或和都是唯一確定的與路徑無關3. 帶權并查集用 fa[x] 記錄父節(jié)點dis[x] 記錄 x 到父節(jié)點路徑上的邊權異或和。通過路徑壓縮find(x) 后 dis[x] 就是 x 到根的異或距離4. 判斷邏輯對于邊 (u, v, w)若 u、v 已在同一集合檢查 dis[u] ^ dis[v] ^ w 是否為 0為 0 說明新環(huán)異或和為偶數(shù)可加入否則會產生奇權環(huán)跳過C 實現(xiàn)class Solution {vectorint fa, dis; // dis[x]: x 到 fa[x] 路徑上的邊權異或和// 帶路徑壓縮的 find調用后 dis[x] 變?yōu)?x 到根的異或距離int find(int x) {if (fa[x] ! x) {int root find(fa[x]);dis[x] ^ dis[fa[x]]; // 累積異或距離fa[x] root;}return fa[x];}public:int numberOfEdgesAdded(int n, vectorvectorint edges) {fa.resize(n);dis.assign(n, 0);for (int i 0; i n; i) fa[i] i;int count 0;for (auto edge : edges) {int u edge[0], v edge[1], w edge[2];int ru find(u), rv find(v);if (ru rv) {// 已在同一集合檢查新環(huán)的異或和// 環(huán)的異或和 dis[u] ^ dis[v] ^ wif ((dis[u] ^ dis[v] ^ w) 0) {count; // 偶權環(huán)可以加入}// 否則產生奇權環(huán)跳過} else {// 不在同一集合合并不會形成環(huán)// 需要讓 dis[u] ^ dis[v] ^ w 0 成立// 即 dis[ru] dis[u] ^ dis[v] ^ wdis[ru] dis[u] ^ dis[v] ^ w;fa[ru] rv;count;}}return count;}};關鍵點解析- 路徑壓縮時的異或更新dis[x] ^ dis[fa[x]] 是因為 x 到根的異或距離 x 到舊父節(jié)點的異或 ⊕ 舊父節(jié)點到根的異或- 合并時的權重設置合并 ru 和 rv 時設置 dis[ru] dis[u] ^ dis[v] ^ w保證合并后 u 和 v 之間的異或距離恰好等于 w- 時間復雜度O(m · α(n))其中 m 是邊數(shù)α 是反阿克曼函數(shù)近似線性- 空間復雜度O(n)示例驗證以 n3, edges[[0,1,1],[1,2,1],[0,2,1]] 為例1. 邊 (0,1,1)0 和 1 不在同一集合合并count12. 邊 (1,2,1)1 和 2 不在同一集合合并count23. 邊 (0,2,1)0 和 2 已在同一集合環(huán)異或和 dis[0]^dis[2]^1 1^1^1 1奇數(shù)跳過最終返回 2與預期一致。需要我?guī)湍阏硪环輲嗖⒉榧惢?加法的通用模板嗎遇到類似題可以直接套用。