洛谷 P1955 [NOI2015] 程序自动分析

// P1955 [NOI2015] 程序自动分析 —— ★ 这一版就能 AC
//
// ★★ 关键的一步是**顺序**：**先把所有 `xᵢ = xⱼ` 全部合并完，再回头验所有 `xᵢ ≠ xⱼ`。**
//   理由一句话：并查集只能合并、不能拆 ——
//   一条「不等」约束在**它出现的那一刻**可能还看不出矛盾，
//   而后面来的「相等」会把两边并到一起。⇒ 边读边判就是错的（本页第 ② 步）。
//
// ⚠ 另一件事：`i, j ≤ 10⁹` 而 `n ≤ 10⁵` ⇒ **必须离散化**（本页第 ③ 步）。
// ⚠ 多组数据，每组之间要清空（本页第 ④ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;                 // 每组最多 2n 个不同的变量
static int fa[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<array<int, 3>> c(n);
        vector<int> vals;
        vals.reserve(2 * n);
        for (int k = 0; k < n; k++) {
            int i, j, e;
            cin >> i >> j >> e;
            c[k] = {i, j, e};
            vals.push_back(i);
            vals.push_back(j);
        }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int cnt = (int)vals.size();
        for (int i = 0; i < cnt; i++) fa[i] = i;          // ★ 只清用到的那一段
        auto id = [&](int v) {
            return (int)(lower_bound(vals.begin(), vals.end(), v) - vals.begin());
        };
        for (auto& q : c) if (q[2] == 1) fa[find(id(q[0]))] = find(id(q[1]));   // ① 先并
        bool ok = true;
        for (auto& q : c)
            if (q[2] == 0 && find(id(q[0])) == find(id(q[1]))) { ok = false; break; }   // ② 再验
        out += ok ? "YES\n" : "NO\n";
    }
    cout << out;
    return 0;
}

// P1955 · 错法 ①：边读边判 —— 顺序错了就全错
//
//   e = 1 ⇒ 立刻合并；e = 0 ⇒ **立刻**看两边是不是已经同根，是就判 NO。
// ⚠ 问题在于：一条「不等」出现的那一刻，把它俩连起来的那些「相等」可能**还没读到**。
//   而并查集只能合并、不能拆 ⇒ 后来的合并没法回头把它判成矛盾。
// ★ 它**恒把 NO 判成 YES**（漏判），答案只会偏「宽松」。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;                 // 每组最多 2n 个不同的变量
static int fa[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<array<int, 3>> c(n);
        vector<int> vals;
        vals.reserve(2 * n);
        for (int k = 0; k < n; k++) {
            int i, j, e;
            cin >> i >> j >> e;
            c[k] = {i, j, e};
            vals.push_back(i);
            vals.push_back(j);
        }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int cnt = (int)vals.size();
        for (int i = 0; i < cnt; i++) fa[i] = i;          // ★ 只清用到的那一段
        auto id = [&](int v) {
            return (int)(lower_bound(vals.begin(), vals.end(), v) - vals.begin());
        };
        bool ok = true;
        for (auto& q : c) {                              // ✗ 一趟走完，读到哪判到哪
            if (q[2] == 1) fa[find(id(q[0]))] = find(id(q[1]));
            else if (find(id(q[0])) == find(id(q[1]))) { ok = false; break; }
        }
        out += ok ? "YES\n" : "NO\n";
    }
    cout << out;
    return 0;
}

// P1955 · 错法 ②：拿取模当离散化
//
//   `fa[i % 1000003]` —— 「反正 i ≤ 10⁹，模一个大质数就当下标好了」。
// ⚠ 这是**哈希**，不是离散化：两个不同的变量模出同一个下标，就被当成了同一个变量。
//   ⇒ 又一次[第 49 章那条](/ch/49-hashing/)：**哈希会错，而且它错得很安静**。
// ★ 顺手写的生成器变量号只有几十个 ⇒ 这一档是**结构性的精确 0**（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;                 // 每组最多 2n 个不同的变量
static int fa[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<array<int, 3>> c(n);
        vector<int> vals;
        vals.reserve(2 * n);
        for (int k = 0; k < n; k++) {
            int i, j, e;
            cin >> i >> j >> e;
            c[k] = {i, j, e};
            vals.push_back(i);
            vals.push_back(j);
        }
        const int MOD = 1000003;                         // ✗ 拿取模当离散化
        for (int v : vals) fa[v % MOD % N] = v % MOD % N;
        auto id = [&](int v) { return v % MOD % N; };
        for (auto& q : c) if (q[2] == 1) fa[find(id(q[0]))] = find(id(q[1]));   // ① 先并
        bool ok = true;
        for (auto& q : c)
            if (q[2] == 0 && find(id(q[0])) == find(id(q[1]))) { ok = false; break; }   // ② 再验
        out += ok ? "YES\n" : "NO\n";
    }
    cout << out;
    return 0;
}