题目大意: 给出 n 个变量互相的相等或不等关系, 求这些关系是否矛盾
思路: 把相等的变量加入并查集, 不等的查询是否合法
eg: 数据很大, 离散化 (然而我用的是 map)
- #include<stdio.h>
- #include<algorithm>
- #include<string.h>
- #include<map>
- using namespace std;
- int fa[10000000],n,sum[10000000],tot,T;
- map<int,int> old,tong;
- struct node
- {
- int x,y,c;
- }a[10000000];
- template<class T>void read(T &x)
- {
- x=0;char ch=getchar();
- while(ch<'0'||ch>'9') ch=getchar();
- while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- }
- int find(int x)
- {
- int p=x,q;
- while(x!=fa[x])
- x=fa[x];
- while(p!=x)
- {
- q=fa[p];
- fa[p]=x;
- p=q;
- }
- return x;
- }
- int main()
- {
- read(T);
- while(T--)
- {
- old.clear();tong.clear();tot=0;bool flag=0;
- read(n);
- for(int i=1;i<=n;i++)
- {
- read(a[i].x);read(a[i].y);read(a[i].c);
- if(tong[a[i].x]==0)
- {
- tong[a[i].x]=1;
- sum[++tot]=a[i].x;
- }
- if(tong[a[i].y]==0)
- {
- tong[a[i].y]=1;
- sum[++tot]=a[i].y;
- }
- }
- sort(sum+1,sum+1+tot);
- for(int i=1;i<=tot;i++) old[sum[i]]=i;
- for(int i=1;i<=n;i++)
- {
- a[i].x=old[a[i].x];
- a[i].y=old[a[i].y];
- }
- for(int i=1;i<=tot;i++) fa[i]=i;
- for(int i=1;i<=n;i++)
- {
- int p=find(a[i].x),q=find(a[i].y);
- if(a[i].c==1&&p!=q) fa[p]=q;
- if(a[i].c!=1&&p==q){flag=1;break;}
- }
- if(flag==1){printf("NO\n");continue;}
- for(int i=1;i<=n;i++)
- {
- int p=find(a[i].x),q=find(a[i].y);
- if(a[i].c==1&&p!=q){flag=1;break;}
- if(a[i].c==0&&p==q){flag=1;break;}
- }
- if(flag==1)printf("NO\n");
- else printf("YES\n");
- }
- return 0;
- }
- bzoj4195(并查集 + 离散化)
来源: http://www.bubuko.com/infodetail-2589134.html