《算法竞赛进阶指南》0x41并查集 NOI2015程序自动分析

题目链接：https://www.acwing.com/problem/content/239/

给出n个变量之间的等式和不等式关系，判断是否存在错误，由于等号具有传递性，不等号不具有，所以可以考虑使用并查集。并查集可以维护图中结点的连通性，在这个问题中得以体现。

其次，这个问题的变量数量少，但是索引大，需要通过离散化进行处理。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn =1000010;
int n,m;
struct node{
    int xi,xj;
    int flag;
}p[maxn];
int fa[maxn*2];
int a[maxn*2];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int get(int x){
    return lower_bound(a+1,a+m+1,x)-a;
}
void Union(int x,int y){
    int fx=find(get(x));
    int fy=find(get(y));
    if(fx==fy)return ;
    fa[fx]=fy;
    return ;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&p[i].xi,&p[i].xj,&p[i].flag);
        a[2*i-1]=p[i].xi;
        a[2*i]=p[i].xj;
    }
    sort(a+1,a+2*n+1);
    m=unique(a+1,a+2*n+1)-(a+1);
    for(int i=1;i<=m;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
        if(p[i].flag)Union(p[i].xi,p[i].xj);
    
    for(int i=1;i<=n;i++)
        if(!p[i].flag && find(get(p[i].xi))==find(get(p[i].xj))){
            puts("NO");
            return     ;    
        }
    puts("YES");
    return ;
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

《算法竞赛进阶指南》0x41并查集 NOI2015程序自动分析

相关推荐