題目
https://www.nowcoder.com/acm/contest/119/A
題目大意
每次查詢告訴你[l,r]之間的數(shù)的異或和，如果遇到不正確的查詢脯宿，輸出查詢編號。
算法思路
- 因為異或和前綴是不影響他的值，所以我們只需要將l和r連線犹褒，以異或值為權(quán)值，帶權(quán)并查集即可大溜。
- 每次查詢?nèi)绻鹟和r在同一集合中化漆，檢查與其值是否相符即可。若不在钦奋，直接相連即可座云。
- 帶權(quán)并查集的操作
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];
/*這里需要想一想；然后只更新了根節(jié)點的值付材，
子節(jié)點的值可以在后續(xù)查詢find的時候更新*/
}
- 為了方便操作朦拖，采用左開右閉（常規(guī)操作）
代碼
#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;
}
