這道題的核心是帶權(quán)并查集將環(huán)邊權(quán)和為偶數(shù)轉(zhuǎn)化為環(huán)上邊權(quán)異或和為 0通過維護(hù)每個(gè)節(jié)點(diǎn)到根的異或距離來判斷新邊是否會形成奇權(quán)環(huán)。核心思路1. 問題轉(zhuǎn)化邊權(quán)為 0 或 1環(huán)的邊權(quán)和為偶數(shù) ? 環(huán)上所有邊權(quán)的異或和為 02. 維護(hù)目標(biāo)如果圖中所有環(huán)的異或和都為 0那么任意兩點(diǎn)間任意路徑的異或和都是唯一確定的與路徑無關(guān)3. 帶權(quán)并查集用 fa[x] 記錄父節(jié)點(diǎn)dis[x] 記錄 x 到父節(jié)點(diǎn)路徑上的邊權(quán)異或和。通過路徑壓縮find(x) 后 dis[x] 就是 x 到根的異或距離4. 判斷邏輯對于邊 (u, v, w)若 u、v 已在同一集合檢查 dis[u] ^ dis[v] ^ w 是否為 0為 0 說明新環(huán)異或和為偶數(shù)可加入否則會產(chǎn)生奇權(quán)環(huán)跳過C 實(shí)現(xiàn)class Solution {vectorint fa, dis; // dis[x]: x 到 fa[x] 路徑上的邊權(quán)異或和// 帶路徑壓縮的 find調(diào)用后 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; // 偶權(quán)環(huán)可以加入}// 否則產(chǎn)生奇權(quá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;}};關(guān)鍵點(diǎn)解析- 路徑壓縮時(shí)的異或更新dis[x] ^ dis[fa[x]] 是因?yàn)?x 到根的異或距離 x 到舊父節(jié)點(diǎn)的異或 ⊕ 舊父節(jié)點(diǎn)到根的異或- 合并時(shí)的權(quán)重設(shè)置合并 ru 和 rv 時(shí)設(shè)置 dis[ru] dis[u] ^ dis[v] ^ w保證合并后 u 和 v 之間的異或距離恰好等于 w- 時(shí)間復(fù)雜度O(m · α(n))其中 m 是邊數(shù)α 是反阿克曼函數(shù)近似線性- 空間復(fù)雜度O(n)示例驗(yà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與預(yù)期一致。需要我?guī)湍阏硪环輲?quán)并查集異或/加法的通用模板嗎遇到類似題可以直接套用。