难度1
em还是一道比较套路的题目。观察发现,如果当\(r_{i}=1\)时他的两把钥匙状态是相同的,当\(r_{i}=0\)时他的两把钥匙状态是不同的,对于这种相同不同的问题可以考虑并差集,状态一样就一样的并在一起,否则就把不一样的并在一起
所以以后看见这些问题(a=b+k,a=!b,a=b)都可以用带权并查集,扩展域并查集等解决。最好所有优化都加上,不然不如dfs
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,a[100005],fa[200005],b[100005][2];
bool sta[100005];
int get(int x){
if(fa[x]!=x) return fa[x]=get(fa[x]);
return fa[x];
}
void merge(int x,int y){
int xi=get(x),yi=get(y);
if(xi!=yi){
fa[xi]=yi;
}
}
void print(){
for(int i=1;i<=2*m;i++){
cout<<get(i)<<" ";
}cout<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m*2;i++){
fa[i]=i;
}
for(int i=1;i<=n;i++){
cin>>sta[i];
}
for(int i=1;i<=m;i++){
cin>>k;
for(int j=1;j<=k;j++){
cin>>x;
if(b[x][0]==0) b[x][0]=i;
else b[x][1]=i;
}
}
for(int i=1;i<=n;i++){
if(sta[i]==0){
merge(b[i][0],b[i][1]+m);
merge(b[i][0]+m,b[i][1]);
}else{
merge(b[i][0],b[i][1]);
merge(b[i][0]+m,b[i][1]+m);
}
//print();
}
for(int i=1;i<=m;i++){
//cout<<get(i)<<" "<<get(i+m)<<endl;
if(get(i)==get(i+m)){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
return 0;
}
标签:yi,xi,思想,get,int,查集,fa,CF776D
From: https://www.cnblogs.com/wuhupai/p/18036283