Codevs 4600 [NOI2015]程序自动分析

/*

并查集+hash判重.

一开始做是建立x和x+n的连线关系.

然后华丽的R+W.

又想到map但是慢啊啊啊啊啊.

最后还是用hash搞.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 2000010

#define mod 2000007

#define mod2 1000007

using namespace std;

int father[MAXN],n,m,tot1,tot2;

struct data

{

    int x;

    int y;

}a[MAXN],w[MAXN];

int read()

{

    int x=0;char ch;ch=getchar();

    while(ch<'0'||ch>'9') ch=getchar();

    while(ch>='0'&&ch<='9')  x=x*10+ch-48,ch=getchar();

    return x;

}

int find(int x)

{

    return x!=father[x]?father[x]=find(father[x]):x;

}

void slove()

{

    int x,y,z;

    n=read();

    tot1=tot2=0;

    for(int i=1;i<=n;i++)

    {

        x=read();y=read();z=read();

        x=((x%mod)+mod2)%mod;

        y=((y%mod)+mod2)%mod;

        m=max(max(x,y),m);

        if(z){

            a[++tot1].x=x;

            a[tot1].y=y;

        }

        else{

            w[++tot2].x=x;

            w[tot2].y=y;

        }

    }

}

bool slove2()

{

    for(int i=1;i<=m;i++)  father[i]=i;

    for(int i=1;i<=tot1;i++)

    {

        int l1=find(a[i].x),l2=find(a[i].y);

        if(l1!=l2) father[l2]=l1;

    }

    for(int i=1;i<=tot2;i++)

    {

        int l1=find(w[i].x),l2=find(w[i].y);

        if(l1==l2)  return false;

    }

    return true;

}

int main()

{

    int t;

    t=read();

    while(t--)

    {

        slove();

        if(slove2()) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}