题目
https://www.nowcoder.com/acm/contest/119/A
题目大意
每次查询告诉你[l,r]之间的数的异或和，如果遇到不正确的查询，输出查询编号。
算法思路
- 因为异或和前缀是不影响他的值，所以我们只需要将l和r连线，以异或值为权值，带权并查集即可。
- 每次查询如果l和r在同一集合中，检查与其值是否相符即可。若不在，直接相连即可。
- 带权并查集的操作
int Find(int x)
{
if(x==fa[x])return x;
int temp=fa[x];
fa[x]=Find(fa[x]);//路径压缩
rnk[x]=rnk[x]^rnk[temp];//更新rnk值
return fa[x];
}
合并操作
int ru=Find(u);
int rv=Find(v);
if(ru!=rv) {
fa[ru]=rv;
rnk[ru]=k^rnk[u]^rnk[v];
/*这里需要想一想；然后只更新了根节点的值，
子节点的值可以在后续查询find的时候更新*/
}
- 为了方便操作，采用左开右闭（常规操作）
代码
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
int fa[N];
ll rnk[N];
void Init(int n)
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
rnk[i]=0;
}
}
int Find(int x)
{
if(x==fa[x])return x;
int temp=fa[x];
fa[x]=Find(fa[x]);
rnk[x]=rnk[x]^rnk[temp];
return fa[x];
}
int main()
{
int n,m;
while(cin>>n>>m){
Init(n+1);
int flag=0;
for(int i=1;i<=m;i++){
int u,v;
ll k;
scanf("%d%d%lld",&u,&v,&k);
v++;
int ru=Find(u);
int rv=Find(v);
if(ru!=rv) {
fa[ru]=rv;
rnk[ru]=k^rnk[u]^rnk[v];
}
else
{
if((rnk[v]^rnk[u])!=k) {flag=1;cout<<i<<endl;}
}
}
if(!flag) cout<<-1<<endl;
}
return 0;
}
