推銷洛谷博客：https://www.luogu.com.cn/article/znmr9iu9

Link：Luogu - P3907

這里默認題目中指的環都是“簡單環”（即沒有“環套環”的情況）。

眾所周知，樹是圖的一種特殊情況，且一定無環。如果我們想要得到一個有環的復雜圖，有一種辦法是考慮先建一棵樹，然后不斷加入非樹邊。

那本題如果要“找環”，我們不妨把這個過程反過來。先對于原圖中每個連通塊都求一棵生成樹，因為任意一個簡單環都可以又一條非樹邊和樹上的一段路徑組成，考慮枚舉非樹邊并判斷即可。

例如上圖，環①可以由樹上路徑 $5?2?4?6?7$ 和非樹邊 $5?7$ 組成；環②可以由樹上路徑 $8?3?9$ 和非樹邊 $8?9$ 組成。

由于異或滿足交換律，可以用樹上前綴和 + LCA 快速取得某條樹上路徑的權值異或和。時間復雜度 $O(n\log n)$。

但其實還可以再優化，設 $s_i$ 表示從根結點到 $i$ 的前綴和，在求 $u?v$ 路徑的加法權值和時公式是 $s_u+s_v?2?s_{\text{lca(u,v)}}$。但因為異或滿足 $x\oplus x=0$，所以在 $s_u\oplus s_v$ 時 $1?\text{lca}(u,v)$ 路徑上的異或和就會被自動抵消掉！這樣我們就無需求 LCA 了。時間復雜度可以做到 $O(n+m)$。

在求生成樹時只要拿一個 $vis$ 數組標記即可，注意特判自環的情況。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;vector<array<int, 2>> G[maxn];   // 鄰接表：鄰接節點，邊權
int s[maxn], p[maxn];            // 到根節點的異或和、記錄屬于的連通塊
bool vis[maxn];                  // 標記數組
set<array<int, 2>> treeE;        // 存儲樹邊的有序對
int now;                         // 連通塊計數器void dfs(int u, int fa){ // 求生成樹+前綴異或和vis[u] = true;p[u] = now;for(auto [v, w] : G[u]){if(v == fa) continue;if(!vis[v]){treeE.insert({min(u, v), max(u, v)}); // 加入生成樹中，存儲時注意大小關系s[v] = s[u] ^ w;dfs(v, u);}}
}bool solve(){ // 在判斷時采取的標準是：如果環不為0一定不行，直接返回；否則雖然當前行但不一定全部都行，繼續檢查int n, m;cin >> n >> m;// 初始化memset(vis, 0, sizeof(vis));memset(s, 0, sizeof(s));memset(p, 0, sizeof(p));treeE.clear();for(auto &u : G) u.clear();now = 0;vector<tuple<int, int, int>> E; // 存儲所有原始邊for(int i = 1; i <= m; i ++){int u, v, w; cin >> u >> v >> w;G[u].push_back({v, w}); G[v].push_back({u, w});E.emplace_back(u, v, w);}// 生成樹+前綴異或和for(int u = 1; u <= n; u ++){if(!vis[u]){now ++; dfs(u, -1);}}// 檢查所有非樹邊+統計答案for(auto [u, v, w] : E){if(u == v){ // 自環if(w != 0) return false;continue;}if(p[u] != p[v]) continue; // 不同連通塊之間無需檢查array<int, 2> e = {min(u, v), max(u, v)};if(!treeE.count(e)){ // 檢查非樹邊if((s[u] ^ s[v]) != w) return false;}}return true;
}int main(){cin.tie(nullptr) -> ios::sync_with_stdio(false);int T; cin >> T;while(T --) cout << (solve()? "Yes" : "No") << "\n";return 0;
}

再給一份暴力找環就 AC 的代碼：

int vis[55];
vector<array<int, 2>> G[55];bool dfs(int u, int val, int s){ // 當前遍歷到u，異或值為val，起點為s時，判定是否正確for(auto [v, w] : G[u]){if(v == s && (val ^ w) != 0) return false; // 又回到自己了，且不為0if(vis[v]) continue;vis[v] = 1;if(!dfs(v, val ^ w, s)) return false;}return true;
}void solve()
{int n, m; cin >> n >> m;for(int i = 1; i <= m; i ++){int a, b, c; cin >> a >> b >> c;G[a].push_back({b, c}), G[b].push_back({a, c});}bool flag = true;for(int i = 1; i <= n; i ++){memset(vis, 0, sizeof vis);vis[i] = 1;flag &= dfs(i, 0, i);if(!flag) break;}cout << (flag? "Yes" : "No") << '\n';for(int i = 1; i <= n; i ++) G[i].clear(); // 清空！
}

當然也可以用什么帶權并查集之類的做。（其實是我沒調過）