官方题解｜隐藏元素

题目解析

本题需要我们根据各个变量 $A_i$ 和 $A_1$ 的关系来推出 $A_i$ 的值。

我们可以根据给出的 $M$ 条信息来构建一个无向图：
对于 $A_i \oplus A_j = k$，我们可以构建一条 $(i, j)$ 的边权为 $k$ 的边。

最后使用 $\tt{DFS}/\tt{BFS}$ 从 $1$ 开始遍历整个图，对于遍历到的每个点 $u$ 其所有的邻接点 $v_i$，那么 $A_{v_i} = A_u \oplus w_{u \rightarrow v_i}$。

遍历结束以后没有遍历到的点，说明无法判断其和 $A_1$ 的关系，输出 $-1$ 即可。

AC代码

C++ AC代码：

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<int> res(n + 1, -1);
    res[1] = 1;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        auto u = q.front(); q.pop();
        for (auto &[v, w] : g[u]) {
            if (res[v] != -1) continue;
            res[v] = res[u] ^ w;
            q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << res[i] << " \n"[i == n];
    return 0;
}

Python AC代码：

from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for i in range(m):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])
res = [-1] * (n + 1)
res[1] = 1
q = deque()
q.append(1)
while q:
    u = q.popleft()
    for v, w in g[u]:
        if res[v] == -1:
            res[v] = res[u] ^ w
            q.append(v)
print(" ".join(map(str, res[1:])))

复杂度分析

建图的时间复杂度为 $\mathrm{O}(M)$，搜索遍历图的复杂度为 $\mathrm{O}(N + M)$。总的时间复杂度为 $\mathrm{O}(N + M)$。