AcWing-237-程序自动分析

问题

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定 n 个形如xi=xj 或 xi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第 1 行包含 1 个正整数 t，表示需要判定的问题个数，注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第 1 行包含 1 个正整数 n，表示该问题中需要被满足的约束条件个数。

接下来 n 行，每行包括 3 个整数 i,j,e，描述 1 个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1，则该约束条件为 xi=xj；若 e=0，则该约束条件为 xi≠xj。

输出格式

输出文件包括 t 行。

输出文件的第 k行输出一个字符串 YES 或者 NO，YES 表示输入中的第 k 个问题判定为可以被满足，NO 表示不可被满足。

数据范围

1≤n≤1000000
1≤i,j≤1000000000

输入样例：

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出样例：

NO
YES

思路

• 离散化＋并查集

先将每组满足相等关系的元素插到同一个集合中，再检查是否满足不等关系，只要有一个不等关系不满足，则该问题不可以被满足，输出 NO，若都满足，则输出 YES。

注意本题中输入的 i,j 的范围太大了，而实际上节点个数最多为 n+1个，则可以考虑使用离散化方法，将 i,j 的范围缩小，从而减少数组开销。

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

const int MAX = 1e6 + 5;

pair<int, int> nodes_eq[MAX], nodes_neq[MAX];
vector<int> nums;

int get_index(int x) { //查找离散化后的下标
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int fa[MAX], n;

void init(int size) {
    for (int i = 0; i < size; ++i) fa[i] = i;
}

int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);  //路径压缩
}

void merge(int x, int y) {
    fa[get(x)] = fa[y]; //将 x 的根节点指向 y 的根节点
}

int main() {
    int t, x, y, e, cnt1, cnt2;
    cin >> t;
    while (t--) {
        cnt1 = 0, cnt2 = 0;
        nums.clear();
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%d", &x, &y, &e);
            if (e) nodes_eq[cnt1++] = {x, y};
            else nodes_neq[cnt2++] = {x, y};
            nums.push_back(x);
            nums.push_back(y);
        }

        //离散化
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

        //初始化并查集
        init(nums.size());  //注意大小为离散化后用到的数字的数量大小

        //合并相等的元素集合
        for (int i = 0; i < cnt1; ++i) {
            auto p = nodes_eq[i];
            int x = get_index(p.first), y = get_index(p.second);    //离散后的下标
            int px = get(x), py = get(y);   //根节点
            if (px != py) merge(x, y);      // x 和 y 不在同一个集合，合并
        }

        //检查是否满足不等关系
        bool st = true;
        for (int i = 0; i < cnt2; ++i) {
            auto p = nodes_neq[i];
            int x = get_index(p.first), y = get_index(p.second);    //离散后的下标
            int px = get(x), py = get(y);   //根节点
            if (px == py) {     //x 和 y　在同一个集合内，则本来不相等的元素相等了，则出错，退出遍历
                st = false;
                break;
            }
        }

        if (st) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}