洛谷 P1892 [BalticOI 2003] 团伙

// P1892 [BalticOI 2003] 团伙 —— ★ 这一版就能 AC
//
// ★★ 关键的一步：**把点数翻倍**。第 i 号点开两个位置：
//     i      = 「i 本人」所在的朋友团
//     i + n  = 「i 的敌人」所在的朋友团（一个**虚**的位置，代表「和 i 敌对的那一派」）
//
//   F p q（朋友）⇒ union(p, q) 且 union(p+n, q+n)     —— 他俩同派，他俩的敌人也同派
//   E p q（敌人）⇒ union(p, q+n) 且 union(p+n, q)     —— p 属于「q 的敌人」那一派，反之亦然
//
//   「敌人的敌人是朋友」不用另外写：p 和 q 是敌人、q 和 r 是敌人
//   ⇒ p 和 r 都被并进了 q+n 那一派，自然成了朋友。
//
// ⚠⚠ 最后数团体数有一个坑，本页作者当场踩了：**不能写 `if (find(i) == i) ans++`** ——
//   一个团体的**根完全可能落在虚点上**（i + n 那一半），那时前 n 个位置里一个「自己是根」的都没有。
//   ⇒ 正确的数法是：把 find(1..n) 的结果扔进一个集合，数**有几个不同的根**（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2005;                 // 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;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') { unite(p, q); unite(p + n, q + n); }
        else { unite(p, q + n); unite(p + n, q); }
    }
    set<int> roots;
    for (int i = 1; i <= n; i++) roots.insert(find(i));     // ★ 数「有几个不同的根」
    cout << roots.size() << '\n';
    return 0;
}

// P1892 · 错法 ①：数团体数时写成 `if (find(i) == i) ans++`
//
// ⚠⚠ **本页作者第一版就是这么写的，官方样例当场打出 2（正确答案 3）。**
// ★ 原因说得清：一个团体的**根完全可能落在虚点上**（`i + n` 那一半）——
//   扩展域并查集里，`unite(p, q + n)` 会让真点挂到虚点下面。
//   那时前 n 个位置里**一个「自己是根」的都没有**，这个团体就被漏数了。
// ⇒ 它总是**少数**，答案恒 ≤ 正解（本页第 ③ 步量了这条）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2005;                 // 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;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') { unite(p, q); unite(p + n, q + n); }
        else { unite(p, q + n); unite(p + n, q); }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) if (find(i) == i) ans++;   // ✗ 根可能落在虚点上
    cout << ans << '\n';
    return 0;
}

// P1892 · 错法 ③：敌对关系只连了一半
//
//   E p q ⇒ union(p, q + n) 且 union(p + n, q)     ← 正解，两条都要
//   E p q ⇒ union(p, q + n)                        ← 这一版只连一条
//
// ⚠ 「敌人的敌人是朋友」靠的正是那两条一起：p 和 r 都并进 q+n 才成为朋友。
//   ★ 而它并不是每组都错（本页第 ④ 步量了触发条件）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2005;                 // 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;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') { unite(p, q); unite(p + n, q + n); }
        else { unite(p, q + n); }                          // ✗ 少了一半
    }
    set<int> roots;
    for (int i = 1; i <= n; i++) roots.insert(find(i));     // ★ 数「有几个不同的根」
    cout << roots.size() << '\n';
    return 0;
}

// P1892 · 另一条正确的路：**不翻倍**，给每个人记一个「已知的敌人」
//
// ★ 只开 n 个位置的普通并查集，外加一个数组 `foe[i]`：
//     E p q ⇒ 若 p 已经记着一个敌人 e，那么 q 和 e 是「同一个人的两个敌人」⇒ **他俩是朋友**，
//              union(q, e)；否则就把 q 记成 p 的敌人。对 q 同样做一遍。
//     F p q ⇒ union(p, q)
//
// ⚠⚠ 有一个非做不可的细节：**`foe[]` 挂在「集合的根」上，而且合并时要一起并** ——
//   按**点**存会一声不吭地漏掉合并（p1892Node.cpp 就是那一版，本页第 ⑤ 步）。
//
// ⇒ 它和扩展域那版**一行代码都不共享**，可答案必须一样 —— 拿它当参照物（本页第 ⑥ 步）。
// ★ 而它顺带说清了扩展域到底在干什么：`i + n` 那个虚点，就是这里的「这一伙的敌人」那一派。
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N], foe[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;
}
/** ★ 合并时把两边记着的「敌人代表」也并起来 —— foe 是**集合**的属性，不是点的 */
static void unite(int a, int b) {
    int x = find(a), y = find(b);
    if (x == y) return;
    fa[x] = y;
    if (foe[x] && foe[y]) unite(foe[x], foe[y]);
    else if (foe[x]) foe[y] = foe[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) { fa[i] = i; foe[i] = 0; }
    for (int i = 0; i < m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') { unite(p, q); continue; }
        int rp = find(p);
        if (foe[rp]) unite(q, foe[rp]); else foe[rp] = q;
        int rq = find(q);
        if (foe[rq]) unite(p, foe[rq]); else foe[rq] = p;
    }
    set<int> roots;
    for (int i = 1; i <= n; i++) roots.insert(find(i));
    cout << roots.size() << '\n';
    return 0;
}

// P1892 · 错法 ⑤：「不翻倍、记一个敌人」—— 但 foe 按**点**存，不是按**根**存
//
// ⚠⚠ **这一版是写这一页时当场踩的坑**，而且它极有迷惑性：
//   「记一个已知敌人」这个技巧本身是对的（见 p1892Two.cpp），
//   可 `foe[]` 必须挂在**集合的根**上、并且在合并时一起并 ——
//   按**点**存的话，p 后来和别人合并成一伙之后，那一伙的敌人信息就散在几个成员身上，
//   下一次 `foe[p]` 是空的，于是**该合并的没合并**。
//
// ★★★ 而这一页最值钱的一条就在这个 bug 上（本页第 ⑤ 步）：
//   **三个精心设计的极端档（全 F / 全 E / 敌对链）全都是精确的 0，
//   抓到它的偏偏是那个最朴素的「F 和 E 随机混着来」的默认档。**
#include <bits/stdc++.h>
using namespace std;

static const int N = 1005;
static int fa[N], foe[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;
}
static void unite(int a, int b) { fa[find(a)] = find(b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) { fa[i] = i; foe[i] = 0; }
    for (int i = 0; i < m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') { unite(p, q); continue; }
        if (foe[p]) unite(q, foe[p]); else foe[p] = q;
        if (foe[q]) unite(p, foe[q]); else foe[q] = p;
    }
    set<int> roots;
    for (int i = 1; i <= n; i++) roots.insert(find(i));
    cout << roots.size() << '\n';
    return 0;
}