0x41 数据结构进阶-并查集：A题 程序自动分析

题目链接：https://ac.nowcoder.com/acm/contest/1031/A

题目描述

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

输入描述:

第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

输入

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

输出

NO
YES

说明

在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。

备注:

1≤n≤100000

1≤i,j≤1000000000

分析：简单并查集，但需进行离散化加速，另外就是初始化要 乘2（WA 4发）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
const int maxn = 1e5 + 7;
int t, n;
int f[maxn << 1], a[maxn << 1];
int x[maxn], y[maxn], op[maxn];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int main() {
    //freopen("in.txt", "r", stdin);
    //ios::sync_with_stdio(false), cin.tie(0);
    t= read(); while (t--) {
        n = read();
        for (int i = 1; i < maxn << 1; ++i)f[i] = i;
        for (int i = 1; i <= n; ++i) {
            x[i] = read(), y[i] = read(), op[i] = read();
            a[i * 2 - 1] = x[i], a[i * 2] = y[i];
        }
        int m = n << 1;
        sort(a + 1, a + 1 + m);
        m = unique(a + 1, a + 1 + m) - a - 1;
        for (int i = 1; i <= n; ++i) {
            int dx = lower_bound(a + 1, a + 1 + m, x[i]) - a;
            int dy = lower_bound(a + 1, a + 1 + m, y[i]) - a;
            if (op[i])    f[find(dx)] = find(dy);
        }
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            int dx = lower_bound(a + 1, a + 1 + m, x[i]) - a;
            int dy = lower_bound(a + 1, a + 1 + m, y[i]) - a;
            if (!op[i] and f[find(dx)] == f[find(dy)]) {
                flag = 1;    break;
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

0x41 数据结构进阶-并查集：A题 程序自动分析

原文：https://www.cnblogs.com/RioTian/p/13414922.html