【洛谷】P1955 程序自动分析_程序自动分析洛谷题解

题目地址：

https://www.luogu.com.cn/problem/P1955

题目描述：
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设$x_1,x_2,x_3,\cdots$代表程序中出现的变量，给定$n$个形如$x_i=x_j$或$x_i\ne x_j$的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\ne x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。现在给出一些约束满足问题，请分别对它们进行判定。

输入格式：
输入的第一行包含一个正整数$t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。对于每个问题，包含若干行：第一行包含一个正整数$n$，表示该问题中需要被满足的约束条件个数。接下来$n$行，每行包括三个整数$i,j,e$，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若$e=1$，则该约束条件为$x_i=x_j$。若$e=0$，则该约束条件为$x_i\ne x_j$。

输出格式：
输出包括$t$行。输出文件的第$k$行输出一个字符串YES或者NO（字母全部大写），YES表示输入中的第$k$个问题判定为可以被满足，NO表示不可被满足。

实际上$n\le 10^6$。

注意到$i,j$的范围远大于$n$的范围，所以需要离散化。考虑所有相等的约束，这些约束可以用并查集维护，并且所有的相等约束是不会彼此矛盾的。然后再去遍历所有的不等约束，如果与某个相等约束有矛盾则说明不可满足，否则遍历完所有约束之后说明可满足。代码如下：

#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 1e6 + 10;
int n, idx, k;
int p[N];
unordered_map<int, int> mp;
pair<int, int> a[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i < N; i++) p[i] = i;
        idx = k = 0;
        mp.clear();

        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int x, y, e;
            scanf("%d%d%d", &x, &y, &e);
            if (!mp.count(x)) mp[x] = ++k;
            if (!mp.count(y)) mp[y] = ++k;
            x = mp[x];
            y = mp[y];

            if (e == 1) p[find(x)] = find(y);
            else a[++idx] = {x, y};
        }

        bool flag = true;
        for (int i = 1; i <= idx; i++)
            if (find(a[i].first) == find(a[i].second)) {
                flag = false;
                break;
            }

        if (flag) puts("YES");
        else puts("NO");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

时间复杂度$O(n{\log }^{\ast }n)$，空间$O(n)$。