CF Mahmoud and a Dictionary
题目描述 ：给你n个单词， 并且有m行每行有一个数字两个单词 数字代表之间的关系，2表示意思相反 ，1表示同义 之后有q行询问 每行两个单词 输出它两的关系
2 ≤ n ≤ 10^5, 1 ≤ m, q ≤ 10^5
分析：典型的带权并差集问题， 带1权值表示反义，0权值表示同义，在更新时用异或和维护他们之间的关系， 当合并时因为两个个方向走到尾 其异或和相等，而两者异或和为0 所以一个点的权值等去另外三个的异或和
ac代码
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+3;
int parent[MAX];
int value[MAX];
map<string,int> word;
int find(int x){
if(x!=parent[x]){
int t=parent[x];
parent[x]=find(parent[x]);
value[x]^=value[t];
}
return parent[x];
}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// FILE *fp;
// fp=fopen("1.txt","r");
int n,m,k;
// fscanf(fp,"%d %d %d",&n,&m,&k);
cin>>n>>m>>k;
for(int i=1;i<=n;i++) parent[i]=i;
memset(value,0,sizeof(value));
int ans=0;
int t;
for(int i=1;i<=n;i++){
string s;
cin>>s;
word[s]=i;
}
for(int i=1;i<=m;i++){
int a;
string s,ss;
cin>>a>>s>>ss;
if(a==1) a=0;
else a=1;
int fs=find(word[s]),fss=find(word[ss]);
if(fs!=fss){
parent[fs]=fss;
// cout<<fs<<' '<<fss<<endl;
value[fs]=value[word[s]]^value[word[ss]]^a;
cout<<"YES"<<endl;
}
else if(value[word[s]]^value[word[ss]]!=a) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
for(int i=1;i<=k;i++){
string s,ss;
cin>>s>>ss;
int parents=find(word[s]),parentss=find(word[ss]);
// cout<<"!!"<<parent[word[s]]<<' '<<parent[word[ss]]<<endl;
if(parents==parentss) if(value[word[s]]^value[word[ss]]) cout<<2<<endl;
else cout<<1<<endl;
else cout<<3<<endl;
}
}
查看30道真题和解析