BZOJ4195：[NOI2015]程序自动分析

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4195

由于等于具有传递性，所以此题可以用并查集完美的解决。

把相等的元素放在一个集合里，不等的判断是不是不在一个集合里即可。

时间复杂度：\(O(\alpha{n})\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1e5+5;

int n,cnt;
int fa[maxn<<1],tmp[maxn<<1];
int a[maxn],b[maxn],opt[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

int find(int x) {
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}

void merge(int a,int b) {
    a=find(a),b=find(b);
    if(a!=b)fa[a]=b;
}

int main() {
    int T=read();
    while(T--) {
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=tmp[i]=read(),b[i]=tmp[i+n]=read(),opt[i]=read();
        sort(tmp+1,tmp+(n<<1)+1);
        cnt=unique(tmp+1,tmp+(n<<1)+1)-tmp-1;
        for(int i=1;i<=cnt;i++)fa[i]=i;
        for(int i=1;i<=n;i++) {
            a[i]=lower_bound(tmp+1,tmp+cnt+1,a[i])-tmp;
            b[i]=lower_bound(tmp+1,tmp+cnt+1,b[i])-tmp;
        }
        bool ans=1;
        for(int i=1;i<=n;i++)
            if(opt[i])merge(a[i],b[i]);
        for(int i=1;i<=n;i++)
            if(!opt[i]&&find(a[i])==find(b[i]))ans=0;
        if(ans)puts("YES");
        else puts("NO");
    }
    return 0;
}

BZOJ4195：[NOI2015]程序自动分析

原文：https://www.cnblogs.com/AKMer/p/10365143.html