题解 | 人人都是好朋友

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
struct node {
    int u, v, w;
    bool operator <(const node& t)const {
        return w > t.w;
    }
};
void slove() {
    int n;
    std::cin >> n;
    std::unordered_map<int, int> mp;
    std::vector<node> a;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        if (!mp[u]) {
            mp[u] = ++cnt;
            u = mp[u];
        } else u = mp[u];
        if (!mp[v]) {
            mp[v] = ++cnt;
            v = mp[v];
        } else v = mp[v];
        a.push_back({u, v, w});
    }
    std::vector<int> fa(cnt + 1);
    auto find = [&](auto&& find, int x)->int{
        return fa[x] == x ? x : fa[x] = find(find, fa[x]);
    };
    for (int i = 1; i <= cnt; i++) fa[i] = i;
    std::sort(a.begin(), a.end());
    for (auto[u, v, w] : a) {
        if (w == 1) {
            if (find(find, u) != find(find, v)) {
                fa[find(find, v)] = find(find, u);
            }
        } else {
            if (find(find, u) == find(find, v)) {
                std::cout << "NO" << endl;
                return ;
            }
        }
    }
    std::cout << "YES" << endl;
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T--)    {
        slove();
    }
    return 0;
}

umap邪修，如果后续数据卡了可以踢我一下。主要就是离散化+并查集板子。