洛谷 P3367 【模板】并查集

// P3367【模板】并查集 —— ★ 这一版就能 AC
//
// 本章第 5、6 步那两句话（路径压缩 ＋ 按秩合并）原样搬过来就是它。
// ⚠ 这一页要讲的不是算法 —— 算法正文已经讲完了 —— 而是**这道题把那两句话的价钱量了出来**：
//   M ≤ 10⁶ 次操作、N ≤ 2×10⁵ 个点 ⇒ **操作数是点数的 5 倍**，
//   路径压缩省下来的那些跳步会被放大 5 倍（本页第 ③ 步）。
//
// ⚠ 输入格式：每行 **Z X Y**（操作类型在最前面），别读成 X Y Z（本页第 ④ 步）。
// ⚠ 输出是单个大写字母 **Y / N**，不是 Yes / No（本页第 ⑤ 步 —— 隔壁 P1551 正好相反）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;
static int fa[N], rk[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}
static char obuf[1 << 16];
static int opos;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void pc(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }

/* ★ 迭代的两趟：先找到根，再把这一路全挂到根上（和正文 fast.cpp 一样） */
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() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; i++) { fa[i] = i; rk[i] = 0; }
    for (int i = 0; i < m; i++) {
        int z = rd(), x = rd(), y = rd();
        int a = find(x), b = find(y);
        if (z == 1) {
            if (a == b) continue;
            if (rk[a] < rk[b]) swap(a, b);      // ★ 矮的挂到高的下面
            fa[b] = a;
            if (rk[a] == rk[b]) rk[a]++;
        } else {
            pc(a == b ? 'Y' : 'N');
            pc('\n');
        }
    }
    flushOut();
    return 0;
}

// P3367 · 错法 ①：读成了 X Y Z —— 操作类型在最前面，不在最后
//
// ⚠ 绝大多数题的格式是「先给数据、后给操作」，这道题反过来。
//   这个错法**每一组都错**，官方样例一测就死。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;
static int fa[N], rk[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}
static char obuf[1 << 16];
static int opos;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void pc(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }

/* ★ 迭代的两趟：先找到根，再把这一路全挂到根上（和正文 fast.cpp 一样） */
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() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; i++) { fa[i] = i; rk[i] = 0; }
    for (int i = 0; i < m; i++) {
        int x = rd(), y = rd(), z = rd();   // ✗ 顺序反了
        int a = find(x), b = find(y);
        if (z == 1) {
            if (a == b) continue;
            if (rk[a] < rk[b]) swap(a, b);      // ★ 矮的挂到高的下面
            fa[b] = a;
            if (rk[a] == rk[b]) rk[a]++;
        } else {
            pc(a == b ? 'Y' : 'N');
            pc('\n');
        }
    }
    flushOut();
    return 0;
}

// P3367 · 错法 ②：输出 Yes / No —— 那是隔壁 P1551 的格式
//
// ⚠ 同一张题单上的两道题，**问的是同一件事，输出格式却不一样**：
//   这道题要单个大写字母 `Y` / `N`，P1551 要 `Yes` / `No`。
//   ⇒ 「上一道的正确写法就是这一道的 bug」在**同一张题单内**又演了一遍。
#include <bits/stdc++.h>
using namespace std;

static const int N = 200005;
static int fa[N], rk[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}
static char obuf[1 << 16];
static int opos;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void pc(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }

/* ★ 迭代的两趟：先找到根，再把这一路全挂到根上（和正文 fast.cpp 一样） */
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() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; i++) { fa[i] = i; rk[i] = 0; }
    for (int i = 0; i < m; i++) {
        int z = rd(), x = rd(), y = rd();
        int a = find(x), b = find(y);
        if (z == 1) {
            if (a == b) continue;
            if (rk[a] < rk[b]) swap(a, b);      // ★ 矮的挂到高的下面
            fa[b] = a;
            if (rk[a] == rk[b]) rk[a]++;
        } else {
            const char* s = (a == b) ? "Yes" : "No";     // ✗ 这是 P1551 的格式
            for (const char* p = s; *p; p++) pc(*p);
            pc('\n');
        }
    }
    flushOut();
    return 0;
}