C128 并查集+离散化 P1955 [NOI2015] 程序自动分析

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct node { int x, y, e; } a[N];
int f[N], cnt;
unordered_map<int, int> v;

int findfa(int x) { return (f[x] == x) ? f[x] : f[x] = findfa(f[x]); }

int id(int x) {
    if (v.count(x)) return v[x];
    else return v[x] = ++cnt;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        v.clear(); memset(f, 0, sizeof(f));
        for (int i = 1; i <= 2 * n; i++) f[i] = i;
        cnt = 0;
        for (int i = 1, x, y, e; i <= n; i++) {
            scanf("%d%d%d", &x, &y, &e);
            x = id(x); y = id(y);
            if (e) f[findfa(x)] = findfa(y);
            a[i] = {x, y, e};
        }
        bool bk = 1;
        for (int i = 1; i <= n; i++) {
            int x = a[i].x, y = a[i].y, e = a[i].e;
            if (e == 0) {
                int tx = findfa(x), ty = findfa(y);
                if (tx == ty) { bk = 0; break; }
            }
        }
        if (bk == 1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}