官解好抽象~
提供一种思路比较清晰的做法。
拆位
看到异或，首先想到拆位。
对于某一位来说，我们已知每条边上异或的结果，即已知两个节点上这一位是否相同。
任意选一个位置，假定它是 \(1\)，DFS 得到其余所有点上的结果，可知此时图上有 \(x\) 个 \(1\)，\(y\) 个 \(0\)。
实际情况有两种，分别是有 \(x\) 个 \(1\)，\(y\) 个 \(0\) 和有 \(x\) 个 \(0\)，\(y\) 个 \(1\)。
在 \([0,n]\) 中，我们已知有 \(p\) 个数字在这一位上为 \(1\)，\(q\) 个数字在这一位上为 \(0\)，考虑以 \(1\) 的个数作为对应关系。
有一下三种情况：
1.\(x=p-1,y=q\) 或 \(x=q,y=p-1\) 因为 \(0\) 的数量对应确定，所以图上的所有数的这一位中少了一个 \(1\)，即被拿掉的数字上这一位为 \(1\)。
2.\(x=p,y=q-1\) 或 \(x=q-1,y=p\) 同理，可知图上所有数中少了一个 \(0\)。
3.若 \(p=q\)，上面两种条件同时成立，我们无法确定哪个对应 \(0\)，哪个对应 \(1\)，故无法分辨。
时间复杂度为 \(O(n\,\,log\,\,m)\)。
CODE
#include<bits/stdc++.h>
#define fst first
#define sec second
#define mkp(a,b) make_pair(a,b)
#define usetime() (double)clock () / CLOCKS_PER_SEC * 1000.0
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int maxn=2e5+5;
void read(int& x){char c;bool f=0;while((c=getchar())<48) f|=(c==45);x=c-48;while((c=getchar())>47) x=(x<<3)+(x<<1)+c-48;x=(f ? -x : x);
}
int cnt[25];
int ans[maxn];
bool vis[maxn];
int n,m;
vector<pii> mp[maxn];
void dfs(int u,int p){for(int i=0;i<(int)mp[u].size();i++){int v=mp[u][i].fst;if(vis[v]) continue;vis[v]=1,ans[v]=((mp[u][i].sec&(1<<p)) ? (!ans[u]) : ans[u]);dfs(v,p);}
}
void solve(){read(n),read(m);if(m==0&&n>=1){printf("-1\n");return;}for(int i=1;i<=n;i++) mp[i].clear();for(int i=1;i<=m;i++){int u,v,w; read(u),read(v),read(w);mp[u].push_back(mkp(v,w)),mp[v].push_back(mkp(u,w));}memset(cnt,0,sizeof(cnt));for(int i=0;i<=n;i++){for(int j=0;j<=22;j++){if(i&(1<<j)) ++cnt[j];}}int p=0;bool spj=0;for(int i=0;i<=22;i++){fill(vis+1,vis+n+1,0);ans[1]=1,vis[1]=1;dfs(1,i);int k=0;for(int j=1;j<=n;j++){k+=ans[j];}if(n+1-cnt[i]==cnt[i]){spj=1; break;}if(k==cnt[i]-1||n-k==cnt[i]-1) p|=(1<<i);}if(spj){printf("-1\n");}else{printf("%d\n",p);}
}
int main(){int t; read(t);while(t--) solve();return 0;
}
//^o^