Original topic link
Ideas
Seeing this question, it is obvious that this question is actually related to graph theory.\(A\)The array is regarded as an undirected graph, each node\(i\)The point right is\(A_i\), every two nodes\(i\)and\(j\)The right between the two is\(A_i \oplus A_j\). We can enumerate every bit of the answer, use BFS (or DFS, the author uses BFS here) to maintain each connected block (because only the nodes in the connected block will affect each other). If there is a conflict between nodes in any connected block, the output will be directly\(-1\)(Because as long as one bit does not match, all answers will be wrong) and end the program. Otherwise, if all nodes satisfy the condition, the answer is recorded and output at the end.
CODE
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int n,m,x[100010],y[100010],z[100010],zy[200010],tp[200010];
vector<pair<int,int> >vec[200010];
int main()
{
ios::sync_with_stdio(0);
(0);
(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x[i]>>y[i]>>z[i]; //Input
vec[x[i]].push_back(make_pair(y[i],z[i])); //Create undirected edge
vec[y[i]].push_back(make_pair(x[i],z[i]));
}
for(int i=0;i<=30;i++) //Enum every bit, because the power of 10 is less than the power of 31 of 2, so only enumeration of 31 is enough
{
memset(tp,-1,sizeof(tp)); //Initialize the tag array, because the two cases of bits are 0 and 1, they can only be initialized to -1
for(int j=1;j<=n;j++)
{
if(tp[j]!=-1) continue; //If it is in a connected block, skip this node
vector<int> ls;
queue<int> q;
tp[j]=0;
(j);
While(!())
{
int l=();
();
ls.push_back(l);
for(auto eg:vec[l]) //Transfer each edge
{
int v=,w=;
if(tp[v]==-1) //If there is no initial value
{
tp[v]=((w>>i)&1)^tp[l]; // Assign the initial value
(v); //BFS
}
else
{
if(tp[v]!=((w>>i)&1)^tp[l]) //Not meet the conditions
{
cout<<-1;
return 0; //End the program
}
}
}
}
int cnt=0;
for(auto v:ls) if(tp[v]==1) cnt++;
if(cnt>()-cnt) for(auto v:ls) tp[v]=1-tp[v]; //This is done because this graph is an undirected graph, and there will be two opposite answers. The question requires the sum of the array A to be the smallest, so we need to make the bit bits the minimum answer to the minimum answer
for(auto v:ls) if(tp[v]==1) zy[v]|=(1<<i); //Update the answer
}
}
for(int i=1;i<=n;i++) cout<<zy[i]<<' '; //Output answer
return 0;
}