程序自动分析

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

思路：这个题目是个模板题，先将相等的用并查集合并，然后再去验证那些不相等的是否相等即可。

          不过这个题的x比较大，要进行离散化。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
int f[4000005],a[4000005],u[4000005],v[4000005];
int get(int x)
{
    if(f[x]==x)
        return x;
    f[x]=get(f[x]);
    return f[x];
}
int fun(int n)//离散化
{
    int k=n%2000003;
    while(a[k]!=n&&a[k])
        k++;
    a[k]=n;
    return k;
}
void merge(int x,int y)
{
    f[get(x)]=get(y);
    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<=4000000;i++)
        {
            f[i]=i;
            a[i]=0;
        }
        int k=0;
        int x,y,z;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            int x1=fun(x);
            int x2=fun(y);
            if(z)
               merge(x1,x2);
            else
            {
                u[++k]=x1;
                v[k]=x2;
            }
        }
        int uu=0;
        for(int i=1;i<=k;i++)
        {
            if(get(u[i])==get(v[i]))
            {
                uu=1;
                break;
            }
        }
        if(uu==1)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}