AcWing 237. 程序自动分析

题目传送门

本题目主要是学习无序离散化+并查集，原因是：
并查集无法开到\(1e9\)的大小,但输入的数字比较稀疏，可以使用无序离散化unordered_map可以将每个输入的数字映射到一个小的范围内，就可以开这样大的数组进行并查集啦~

#include 
using namespace std;

const int N = 2000010;

int n, m;
//结构体
struct Query {
    int x, y, e;
} query[N];

//无序离散化
unordered_map S;
int get(int x) {
    if (S.count(x) == 0) S[x] = ++n; // x映射为第n个数字
    return S[x];
}

//最简并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); //路径压缩
    return p[x];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        //多组测试数据，需要每次从头开始，清空
        n = 0;
        S.clear();
        cin >> m;
        // m组数据全部读入，通过get计算离散化后的对应的位置号（指并查集数组的位置）
        for (int i = 0; i < m; i++) {
            int x, y, e;
            cin >> x >> y >> e;
            query[i] = {get(x), get(y), e};
        }
    
        for (int i = 1; i <= n; i++) p[i] = i;

        // 合并所有相等约束条件
        for (int i = 0; i < m; i++)
            if (query[i].e == 1) {
                int pa = find(query[i].x), pb = find(query[i].y);
                p[pa] = pb;
            }

        // 检查所有不等条件
        bool has_conflict = false;
        for (int i = 0; i < m; i++)
            if (query[i].e == 0) {
                int pa = find(query[i].x), pb = find(query[i].y);
                if (pa == pb) {
                    has_conflict = true;
                    break;
                }
            }

        if (has_conflict)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}