题解 | 程序自动分析

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> parent, sizes;
    int n, setCount;
    UnionFind(int _n) : n(_n), setCount(_n), parent(_n), sizes(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int Find(int a) {
        if (parent[a] != a) parent[a] = Find(parent[a]);
        return parent[a];
    }
    bool Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return false;
        if (sizes[rx] > sizes[ry]) swap(rx, ry);
        parent[rx] = ry;
        sizes[ry] += sizes[rx];
        setCount--;
        return true;
    }
};

void solve(int testcase) {
    int n;
    cin >> n;
    vector<tuple<int, int, int>> edges;
    unordered_set<int> S;
    for (int i = 0; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        S.insert(u);
        S.insert(v);
        edges.emplace_back(u, v, w);
    }
    vector<int> nodes(S.begin(), S.end());
    unordered_map<int, int> d;
    for (int i = 0; i < nodes.size(); i++) {
        d[nodes[i]] = i;
    }
    UnionFind uf(nodes.size());
    vector<pair<int, int>> uneq;
    for (auto& [u, v, e] : edges) {
        if (e == 1) {
            uf.Union(d[u], d[v]);
        } else {
            uneq.emplace_back(d[u], d[v]);
        }
    }
    for (auto& [u, v] : uneq) {
        if (uf.Find(u) == uf.Find(v)) {
            cout << "NO" << "\n";
            return;
        }
    }
    cout << "YES" << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(nullptr);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        solve(t);
    }
    return 0;
}

离散化+并查集