题解：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\cdot 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; // 又回到自己了，且不为0
        if(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(); // 清空！
}

当然也可以用什么带权并查集之类的做。（其实是我没调过）