H 人人都是好朋友

本题考查了并查集+离散化
题干中“如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的”---->并查集
关于并查集可看看CSDN：https://blog.csdn.net/qq_41593380/article/details/81146850
“手下1e9个”说明直接使用hash和map并不适用，需要考虑进行 离散化 处理
即：将题目中出现的数据整合起来，进行去重处理（对于vector可考虑直接使用unique函数）

1.读入数据，对出现过的“下属”进行存储；
2.对下属进行排序；
3.进行去重处理；

For(i, 1, n) {
            cin >> R[i].a >> R[i].b >> R[i].f;
            a[++cnt] = R[i].a, a[++cnt] = R[i].b;
        }
        sort(a + 1, a + cnt + 1);
        For(i, 1, cnt) { if (a[i] != a[ncnt]) a[++ncnt] = a[i]; }

1.初始化并查集

    For(i, 1, ncnt) vis[i] = i;

1.针对友好进行“连接”，使得其有共同“头”

        For(i, 1, n) {
            if (!R[i].f) continue;
            int aa = lower_bound(a + 1, a + 1 + ncnt, R[i].a) - a;
            int bb = lower_bound(a + 1, a + 1 + ncnt, R[i].b) - a;
            int x = find(aa), y = find(bb);
            if (x != y) vis[y] = x;
        }

1.对敌对关系进行判断，确定是否冲突（“头”相同就冲突）

        bool f = true;
        For(i, 1, n) {
            if (R[i].f) continue;
            int aa = lower_bound(a + 1, a + 1 + ncnt, R[i].a) - a;
            int bb = lower_bound(a + 1, a + 1 + ncnt, R[i].b) - a;
            int x = find(aa), y = find(bb);
            if (x == y) { f = false; break; }
        }

总代码如下

#pragma warning (disable :4996)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-10;
#define For(i,n,m) for(int i=n;i<=m;++i)

struct Node { int a, b, f; };
Node R[1000100];
int a[2000100], vis[2000100];
int n, t;
int find(int a) {
    return vis[a] == a ? a : vis[a] = find(vis[a]);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> t;
    while (t--) {
        cin >> n;
        int cnt(0), ncnt(0);
        For(i, 1, n) {
            cin >> R[i].a >> R[i].b >> R[i].f;
            a[++cnt] = R[i].a, a[++cnt] = R[i].b;
        }
        sort(a + 1, a + cnt + 1);
        For(i, 1, cnt) { if (a[i] != a[ncnt]) a[++ncnt] = a[i]; }
        For(i, 1, ncnt) vis[i] = i;
        For(i, 1, n) {
            if (!R[i].f) continue;
            int aa = lower_bound(a + 1, a + 1 + ncnt, R[i].a) - a;
            int bb = lower_bound(a + 1, a + 1 + ncnt, R[i].b) - a;
            int x = find(aa), y = find(bb);
            if (x != y) vis[y] = x;
        }
        bool f = true;
        For(i, 1, n) {
            if (R[i].f) continue;
            int aa = lower_bound(a + 1, a + 1 + ncnt, R[i].a) - a;
            int bb = lower_bound(a + 1, a + 1 + ncnt, R[i].b) - a;
            int x = find(aa), y = find(bb);
            if (x == y) { f = false; break; }
        }
        if (f) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}