【BZOJ4195】程序自动分析

    并查集+Hash。

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn=1000010;
 
map <int,int> M;
int f[maxn<<1];
int x[maxn],y[maxn],z[maxn];
int n,m,cnt;
 
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
 
int Find(int x) {return f[x]==x?x:f[x]=Find(f[x]);}
void Union(int x,int y) {f[Find(x)]=Find(y);}
 
int main()
{
    int T;
    read(T);
    while (T--)
    {
        M.clear();
        n=cnt=0;
        read(m);
        for (int i=1;i<=m;i++) read(x[i]),read(y[i]),read(z[i]);
        for (int i=1;i<=m;i++)
        {
            if (!M[x[i]]) M[x[i]]=++cnt;
            if (!M[y[i]]) M[y[i]]=++cnt;
        }
        for (int i=1;i<=cnt;i++) f[i]=i;
        for (int i=1;i<=m;i++) if (z[i]==1) Union(M[x[i]],M[y[i]]);
        int flag=0;
        for (int i=1;i<=m && !flag;i++) if (z[i]==0 && Find(M[x[i]])==Find(M[y[i]])) flag=1;
        if (flag) puts("NO");else puts("YES");
    }
    return 0;
}