水水水~

xiaoyi_zeng · 2025-12-10 21:42:25 · 题解

P3907 题解

水水水

这数据开 1 \leq T \leq 10 和 1 \leq n,m \leq 50 不是放人水过去吗。

题意

很简单的题，给定一个无向带权图，判断是否所有环的边的异或和是否为 0。

思路

尽管这道题目随便放人过去，但是好歹咱么有点素质好不好。

我不写 O(n^3) 和 O(n^2) 的做法了，都挺朴素的。

来发 O(n) 如何！

（这个人尝试在数据范围 50 的题目中搞出一种线性的算法。）

不过，我真就想出来了！

因为题目中研究的是环，然而我们知道我们可以只考虑每个点度数为 2 的环，其他环都是由小环构成的。所以首先，我们遍历这张图，构建一颗 dfs 树。这样每一条返祖边都构成一个环。

考虑如何计算这个环的异或和，显然可以边 dfs 边维护一个前缀和。

不妨设当前返祖边连接的是 x 和 y，边权是 val。

那么当前环的异或和是 pre_x \bigoplus pre_y \bigoplus val，只需要判断该值是否等于 0 就可以了。

代码

:::success[code]

// 21:18
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int T, n, m;
bool vis[N];
int sum[N];
vector <pair<int, int>> g[N];

bool dfs(int f, int u){
    vis[u] = true;

    for (auto t : g[u]){
        int v = t.first, w = t.second;
        if (v == f) continue;

        if (vis[v]){
            int t = sum[u] ^ sum[v] ^  w;
            if (t != 0) return false;
            continue;
        }

        sum[v] = sum[u] ^ w;
        if (!dfs(u, v)) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> T;
    while (T -- ){
        memset(vis, false, sizeof vis);
        memset(sum, 0, sizeof sum);

        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) g[i].clear();
        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});
        }

        bool flag = true;
        for (int i = 1; i <= n; i ++ )
            if (!vis[i])
                if (!dfs(0, i)){
                    flag = false;
                    break;
                }

        if (flag) cout << "Yes\n";
        else cout << "No\n";
    }
}

:::