【并查集】B001_AW_自动程序分析（不要求顺序时的离散化）

一、自动程序分析

考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。
例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
数据范围
1≤n≤1000000
1≤i,j≤1000000000
输入样例：

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例：
NO
YES

方法一：离散化+并查集

x 最多会有 1e9 个，但 n 最大为 1e6，所以有 1e9-2e6 个数是可以不用的，故需要对数据进行离散化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5;
struct node{
    int u,v,e;
};
int id;
node A[N];
int fa[N];
unordered_map<int, int> m;
int get(int u) {
    if (m.find(u)==m.end()) m[u]=++id;
    return m[u];
}
int find(int u) {
    return fa[u]==u ? u : fa[u]=find(fa[u]);
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin>>t;
    while (t--) {
        int n,u,v,e; cin>>n;
        for (int i=0; i<n; i++) {
            cin>>u>>v>>e; 
            A[i]={get(u), get(v), e};
        }
        for (int i=1; i<=id; i++) fa[i]=i;
        for (int i=0; i<n; i++) if (A[i].e) {
            int fa_u=find(A[i].u), fa_v=find(A[i].v);
            if (fa_u != fa_v) {
                fa[fa_u]=fa_v;
            }
        }
        bool valid=true;
        for (int i=0; i<n; i++) if (!A[i].e) {
            int fa_u=find(A[i].u), fa_v=find(A[i].v);
            if (fa_u == fa_v) {
                valid=false;
                break;
            }
        }
        cout << (valid ?  "YES" : "NO") << '\n';
        m.clear();
    }
    return 0;
}

复杂度分析

• Time：\(O(nlogn)\)，
• Space：\(O(n)\)，