题目大意：给出n个变量互相的相等或不等关系，求这些关系是否矛盾
思路：把相等的变量加入并查集，不等的查询是否合法
eg：数据很大，离散化（然而我用的是map）
#include #include #include #include using namespace std; int fa[],n,sum[],tot,T; map old,tong; struct node { int x,y,c; }a[]; templatevoid read(T &x) { x=;char ch=getchar(); while(ch<''||ch>'') ch=getchar(); while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);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=;bool flag=; read(n); for(int i=;i<=n;i++) { read(a[i].x);read(a[i].y);read(a[i].c); if(tong[a[i].x]==) { tong[a[i].x]=; sum[++tot]=a[i].x; } if(tong[a[i].y]==) { tong[a[i].y]=; sum[++tot]=a[i].y; } } sort(sum+,sum++tot); for(int i=;i<=tot;i++) old[sum[i]]=i; for(int i=;i<=n;i++) { a[i].x=old[a[i].x]; a[i].y=old[a[i].y]; } for(int i=;i<=tot;i++) fa[i]=i; for(int i=;i<=n;i++) { int p=find(a[i].x),q=find(a[i].y); if(a[i].c==&&p!=q) fa[p]=q; if(a[i].c!=&&p==q){flag=;break;} } if(flag==){printf("NO\n");continue;} for(int i=;i<=n;i++) { int p=find(a[i].x),q=find(a[i].y); if(a[i].c==&&p!=q){flag=;break;} if(a[i].c==&&p==q){flag=;break;} } if(flag==)printf("NO\n"); else printf("YES\n"); } return ; }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章
