题解 | 人人都是好朋友

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// const ll len = 1e9;
struct E {
    int a, b, c;
    E() {}
    E(int _a, int _b, int _c): a(_a), b(_b), c(_c) {}
};
void solve() {
    ll n;cin >> n;
    vector<ll> node;
    vector<E> es;
    for(int i = 1;i <= n;i++) {
        ll a, b,c;cin >> a >> b >> c;
        es.emplace_back(a, b, c);
        node.push_back(a);
        node.push_back(b);
    }
    sort(node.begin(), node.end());
    node.erase(unique(node.begin(), node.end()), node.end());
    auto gv = [&](ll q) -> ll {
        return lower_bound(node.begin(), node.end(), q) - node.begin();
    };
    vector<vector<pair<int, int>>> gra(node.size());
    for (E& e : es) {
        // cout << gv(e.a) << " " << gv(e.b) << " " << e.c << '\n';
        gra[gv(e.a)].emplace_back(gv(e.b), e.c);
        gra[gv(e.b)].emplace_back(gv(e.a), e.c);
    }
    vector<bool> vis(node.size()), color(node.size());
    int fd = 1;
    function<void(ll)> dfs = [&](ll u) -> void {
        vis[u] = 1;
        for(auto & k: gra[u]) {
            ll v = k.first,c = k.second;
            if(vis[v]) {
                int tp = 1;
                if (color[v] == color[u]) tp =1;
                else tp = 0;
                if (tp != c) {
                    cout << "NO\n";
                    fd = 0;
                    return ;
                }
            }
            else {
                if(c == 1) color[v] = color[u];
                else color[v] = color[u]^1;
                dfs(v);
                if(fd == 0) return;
            }
        }
    };
    for(int i : node) {
        i = gv(i);
        if(!vis[i]) {
            color[i] = 0;
            dfs(i);
        }
        if(fd == 0) return;
        // cout << 1 << " ";
    }
    if(fd) cout << "YES\n";
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;cin >> t;
    while(t--) solve();
    return 0;
}