BZOJ 4195 程序自动分析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 2000500
using namespace std;
int t,n,father[maxn],stack[maxn],tot=0;
int a[maxn],b[maxn],c[maxn];
int cnt;
int hash(int x)
{
    return lower_bound(stack+1,stack+cnt+1,x)-stack;
}
int getfather(int x)
{
    if (x!=father[x])
        father[x]=getfather(father[x]);
    return father[x];
}
void unionn(int a,int b)
{
    int f1=getfather(a),f2=getfather(b);
    if (f1!=f2) father[f1]=f2;
}
bool judge(int a,int b)
{
    int f1=getfather(a),f2=getfather(b);
    if (f1!=f2) return true;
    return false;
}
void work()
{
    int flag=1;tot=0;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        stack[++tot]=a[i];stack[++tot]=b[i];
    }
    sort(stack+1,stack+tot+1);
    cnt=unique(stack+1,stack+tot+1)-stack-1;
    for (int i=1;i<=cnt;i++) father[i]=i;
    for (int i=1;i<=n;i++)
    {
        if (c[i]==1) 
            unionn(hash(a[i]),hash(b[i]));
    }
    for (int i=1;i<=n;i++)
    {
        if (c[i]==0)
        {
            if (judge(hash(a[i]),hash(b[i]))==false) 
                flag=0;
        }
    }
    if (flag==0) printf("NO\n");
    else printf("YES\n");
}
int main()
{
    scanf("%d",&t);
    for (int i=1;i<=t;i++)
        work();
    return 0;
}