隐藏元素｜拓扑排序变型

第五题 - A23470.隐藏元素

题目链接跳转：A23470.隐藏元素

先讲一个运算法则 ，如果 $A_i \oplus A_j = k$，那么 $A_i \oplus k = A_j$。因此，当我们知道了 $A_1 = 1$ 的时候，我们就可以推出所有有关 $A_1$ 的线索的另一个数字 $A_j$ 的值。一旦确定了一个数字，就可以确定所有与之有关联的数字（线索）。

为了方便起见，我们可以建立一个无向图，这样子就可以通过类似拓扑排序的方式按照顺序一个一个地推断出剩余的未知数。如果有一条线索 $A_i\ A_j\ K$，那么我们就在 $A_i$ 和 $A_j$ 直接连接一条无向边，权值为 $k$，最后对这个图从 $1$ 点开始进行拓扑排序就可以了。

需要注意的是，一个点如果已经被访问过的话，就不需要再被访问了，用 vis 数组记录一下就可以了。本题的 AC 代码如下：

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
int n, m;
struct node{
    int to, k;
};
int ans[N];
vector<node> G[N];

void bfs(){
    queue<int> que;
    que.push(1);
    // 广度优先搜索/拓扑排序
    while(!que.empty()){
        int t = que.front();
        que.pop();
        for (int i=0; i<G[t].size(); i++){
            node tmp = G[t][i];
            if (ans[tmp.to] != -1) continue;
            ans[tmp.to] = ans[t] ^ tmp.k;
            que.push(tmp.to);
        }
    }
    return ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        // 建图：注意边一定是双向的。
        // 由a和c可以推出b，同时也可以由b和c推出a。
        G[a].push_back((node){b, c});
        G[b].push_back((node){a, c});
    }
    memset(ans, -1, sizeof ans);
    ans[1] = 1; bfs();
    for (int i=1; i<=n; i++) 
        cout << ans[i] << " ";
    return 0;
}

本题的 Python 代码如下：

import queue

n, m = map(int, input().split())
G = [[] for _ in range(n+1)]
ans = [-1 for i in range(n+1)]
ans[1] = 1

for i in range(m):
	u, v, w = map(int, input().split())
	G[u].append((v, w))
	G[v].append((u, w))

que = queue.Queue()
que.put(1)

while que.qsize() > 0:
	t = que.get()
	for to in G[t]:
		if ans[to[0]] != -1:
			continue
		ans[to[0]] = ans[t] ^ to[1]
		que.put(to[0])

for i in range(1, n+1):
	print(ans[i], end=" ")
	

以上算法基于 广度优先搜索/拓扑排序 实现，该算法的时间复杂度约为 $O(M)$。