并查集

// 标准答案 —— 完全不碰并查集：每次查询现场 BFS 一遍
//
// 为什么它存在：正解（并查集）想的是「维护一片森林，把信息一路攒下来」。
// 要是标准答案也维护森林，两份代码就是同一个思路写了两遍 ——
// 只能验出打字错误，验不出想法错误（第 9、15、34、35 章那条）。
//
// 所以这一份**什么都不攒**：把每次「合并」当成一条边存下来，
// 每次查询就拿现有的边**现场建图**、从 a 出发 BFS 一遍，看 b 在不在里面；
// 最后那个连通块个数也是重新 BFS 数出来的。
//
// ★ 注意 BFS 里**一次 break 都没有**：哪怕半路就撞见了 b，也要把 a 的连通块整个走完。
//   （第 31 章：「找到第一个就 break」会让暴力假装自己不慢；
//    第 35 章补的后半句：标准答案要挑「没有 break」的那个思路。）
//
// 复杂度 O(q × (n+m))：q 是查询次数。
//
// 输入：第一行 n m；接下来 m 行，每行 "1 a b"（把 a、b 所在的两族合并）
//       或 "2 a b"（问 a、b 现在连不连通）。
// 输出：每个查询一行 Y / N；最后一行输出当前的连通块个数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<pair<int, int>> edges;              // 已经执行过的合并，全都当成无向边攒着
    vector<vector<int>> g(n + 1);
    vector<char> vis(n + 1, 0);

    auto rebuild = [&]() {                     // ★ 每次查询都从零建一遍图：它一点历史都不留
        for (int i = 1; i <= n; i++) g[i].clear();
        for (auto [u, v] : edges) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    };
    auto bfs = [&](int s) {                    // 从 s 出发把整个连通块标满（★ 中途绝不 break）
        vis[s] = 1;
        vector<int> q{s};
        for (size_t h = 0; h < q.size(); h++) {
            int u = q[h];
            for (int v : g[u])
                if (!vis[v]) { vis[v] = 1; q.push_back(v); }
        }
    };

    string out;
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {                         // 合并：只是把边记下来，什么都不算
            edges.push_back({a, b});
            continue;
        }
        rebuild();
        fill(vis.begin(), vis.end(), 0);
        bfs(a);
        out += (vis[b] ? 'Y' : 'N');
        out += '\n';
    }

    rebuild();                                 // 最后再数一遍连通块
    fill(vis.begin(), vis.end(), 0);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) { cnt++; bfs(i); }
    out += to_string(cnt);
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 路径压缩 + 按秩合并
//
// ⚠ 并查集的基本操作第 34 章已经讲完了（dsu.cpp 那一小节：find 是「一路往上找祖宗」，
//   unite 是「把两族的**祖宗**接起来」），这一章不再重复讲一遍。
//   这一份要看的是**另外两句话**，它们俩才是这一章的全部内容：
//
//     ① 路径压缩：find 找到祖宗之后，把这一路上的点**全部直接挂到祖宗身上**，下次一步到位；
//     ② 按秩合并：合并时**矮的那棵挂到高的那棵下面**（rk[x] 是 x 这棵树高度的上界）。
//
//   两句加起来，每次操作的**均摊**代价是 O(α(n))。α 是反阿克曼函数，
//   在 n < 2^65536 的范围里 α(n) ≤ 5 —— 所以它「几乎是常数」，但**它不是常数**，
//   而且这个 α 和第 35 章那个「每个元素进出各一次」一样，是**均摊**出来的：
//   单独某一次 find 完全可以很贵，贵的那几次会被后面变便宜的那些摊掉。
//
// ★ 这一章真正要讲的事情在这里：**上面两句话谁都不影响答案，只影响速度。**
//   把 ② 写反、把 ① 写成一句什么都不干的空话，程序照样**每组都给对的答案** ——
//   对拍一轮都抓不到（第 9 步有现场）。要抓它们只能靠计数器（count.cpp）。
//
// find 这里写成**迭代的两趟**（先找到根，再回头把路上的点挂过去）：
// 递归版更短，可在「不压缩」的那份上会爆栈（deep.cpp 是现场，接第 30 章那条）——
// 为了让三条曲线量的是同一件事，这一章统一写迭代版。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> fa, rk;

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);

    if (!(cin >> n >> m)) return 0;
    fa.resize(n + 1);
    rk.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;
    int cnt = n;                               // 连通块个数：一开始每个点自成一块

    string out;
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        int ra = find(a), rb = find(b);
        if (op == 1) {
            if (ra == rb) continue;            // ⚠ 已经在一族里了，什么都别做（漏了这句，cnt 就错）
            if (rk[ra] > rk[rb]) swap(ra, rb); // ★ 按秩合并：保证 ra 那棵不比 rb 那棵高
            fa[ra] = rb;                       //   矮的挂到高的下面 —— 树高就不会涨
            if (rk[ra] == rk[rb]) rk[rb]++;    //   只有一样高时，接起来才真的高了一层
            cnt--;
        } else {
            out += (ra == rb ? 'Y' : 'N');
            out += '\n';
        }
    }
    out += to_string(cnt);
    out += '\n';

    cout << out;
    return 0;
}

// ★ 这一章的主角：**数一数 find 到底往上跳了多少步**
//
// 为什么它存在：这一章要区分的那些写法（压不压缩、按不按秩、方向反没反）
// **全都不影响答案** —— 对拍在它们身上一轮都抓不到（第 9 步那张表）。
// 秒表也不好使：数据小的时候都是 0.00 秒，数据大的时候又混进了读入和缓存的影响。
//
//   ★ 所以这一章用的尺子是**计数器**：find 里那句「往上走一格」执行了多少次。
//     （第 21 章 stairsCount.cpp 同款：**能数次数就别掐表**，次数是可复现的，秒数不是。）
//
// 口径（正文里也要写清楚，否则这张表没法读）：
//   · 「跳步数」= 执行 `x = fa[x]` 的总次数。**路径压缩的第二趟也算** ——
//     那是实打实的开销，不能因为它是「顺手做的好事」就白送。
//   · 「单次最多」= 某一次 find 里跳得最多的那一次，用来对照第 6 步那条
//     「只按秩合并 ⇒ 树高 ≤ log₂ n」的证明。
//   · 「最终树高」= 全部操作做完之后，森林里最深的那个点有多深。
//     ⚠ 量它的那趟遍历**不计进跳步数**（第 29、32 章那条：**量之前先确认你量的就是它**）。
//
// 用法：./count < 数据            打印那张对比表
//       ./count read < 数据       ★ 只把输入读完就退出，什么都不算
//                                 （用来确认「量到的确实是算法，不是读入」）
//       ./count csv  < 数据       同一批数字，一行一种写法，给脚本和 check:viz 读

#include <bits/stdc++.h>
using namespace std;

// 按显示宽度补空格：ASCII 算 1 格，汉字算 2 格（setw 数的是字节，对不齐）
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

enum Mode { NAIVE, FAKE, ONCE, COMP, HALF, RANKONLY, WRANK, FAST };

struct Dsu {
    Mode mode;
    vector<int> fa, rk;
    long long steps = 0;                       // 往上走了多少格
    int most = 0;                              // 单次 find 走得最多的那一次

    void init(int n) {
        fa.resize(n + 1);
        rk.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) fa[i] = i;
    }

    int find(int x) {
        int walked = 0;
        int r = x;
        if (mode == HALF) {                    // 路径减半：一趟走完，边走边挂到爷爷身上
            while (fa[r] != r) {
                fa[r] = fa[fa[r]];
                r = fa[r];
                walked++;
            }
        } else {
            while (fa[r] != r) { r = fa[r]; walked++; }        // 第一趟：找到祖宗
            if (mode == FAKE) {
                fa[r] = r;                     // ✗ 空话：此刻 r 就是根
            } else if (mode == ONCE) {
                if (fa[x] != r) { fa[x] = r; }  // ✗ 只压了起点这一个（写错顺序的下场）
            } else if (mode == COMP || mode == WRANK || mode == FAST) {
                int y = x;
                while (fa[y] != r) {           // 第二趟：真正的路径压缩（这一趟也要记账）
                    int ny = fa[y];
                    fa[y] = r;
                    y = ny;
                    walked++;
                }
            }
        }
        steps += walked;
        most = max(most, walked);
        return r;
    }

    void unite(int ra, int rb) {               // 传进来的已经是两个**不同的**祖宗
        bool byRank = (mode == RANKONLY || mode == FAST || mode == WRANK);
        if (byRank) {
            if (mode == WRANK ? (rk[ra] < rk[rb]) : (rk[ra] > rk[rb])) swap(ra, rb);
            fa[ra] = rb;
            if (rk[ra] == rk[rb]) rk[rb]++;
        } else {
            fa[ra] = rb;
        }
    }

    int deepest() const {                      // ⚠ 这趟遍历不计进 steps
        int mx = 0;
        for (size_t i = 1; i < fa.size(); i++) {
            int d = 0, x = (int)i;
            while (fa[x] != x) { x = fa[x]; d++; }
            mx = max(mx, d);
        }
        return mx;
    }
};

int main(int argc, char** argv) {
    // ⚠ 读入的写法必须和 fast.cpp / naive.cpp 完全一致，否则 `./count read` 量出来的
    //   「读入要多久」和它们对不上（第 32 章那条：两份代码的 I/O 设置不一样，量的就是读入速度）。
    //   这里输出只用 printf、不用 cout，所以关掉 sync 是安全的（第 26 章那条混用的坑）。
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> ops(m);
    int merges = 0, queries = 0;
    for (auto& o : ops) {
        cin >> o[0] >> o[1] >> o[2];
        (o[0] == 1 ? merges : queries)++;
    }

    if (argc > 1 && string(argv[1]) == "read") {           // ★ 只读入，什么都不算
        printf("只读入：n = %d，操作 %d 次（合并 %d，查询 %d）—— 一步都没跳\n",
               n, m, merges, queries);
        return 0;
    }

    struct Row { Mode mode; const char* name; const char* note; };
    const vector<Row> rows = {
        {NAIVE,    "naive",        "不压缩、不按秩"},
        {FAKE,     "fakeCompress", "✗ 压了个寂寞"},
        {ONCE,     "wrongOnce",    "✗ 只压了第一个点"},
        {COMP,     "compress",     "只路径压缩"},
        {HALF,     "half",         "路径减半（对的）"},
        {RANKONLY, "rankOnly",     "只按秩合并"},
        {WRANK,    "wrongRank",    "✗ 按秩方向反 + 压缩"},
        {FAST,     "fast",         "压缩 + 按秩（正解）"},
    };

    string gold;
    vector<long long> steps(rows.size());
    vector<int> most(rows.size()), deep(rows.size());
    vector<string> ans(rows.size());

    for (size_t i = 0; i < rows.size(); i++) {
        Dsu d;
        d.mode = rows[i].mode;
        d.init(n);
        int cnt = n;
        string out;
        for (auto& o : ops) {
            int ra = d.find(o[1]), rb = d.find(o[2]);
            if (o[0] == 1) {
                if (ra == rb) continue;
                d.unite(ra, rb);
                cnt--;
            } else {
                out += (ra == rb ? 'Y' : 'N');
            }
        }
        out += "/" + to_string(cnt);
        steps[i] = d.steps;
        most[i] = d.most;
        deep[i] = d.deepest();
        ans[i] = out;
        if (rows[i].mode == FAST) gold = out;
    }

    if (argc > 1 && string(argv[1]) == "csv") {            // 给脚本读的：一行一种写法
        for (size_t i = 0; i < rows.size(); i++)
            printf("%s,%lld,%d,%d,%s\n", rows[i].name, steps[i], most[i], deep[i], ans[i].c_str());
        return 0;
    }

    printf("n = %d，操作 %d 次（合并 %d 次，查询 %d 次）\n\n", n, m, merges, queries);
    printf("%s  %s  %s  %s  %s  %s\n",
           padDisp("写法", 14).c_str(), padDisp("说明", 24).c_str(),
           padDisp("find 跳步数", 14).c_str(), padDisp("单次最多", 10).c_str(),
           padDisp("最终树高", 10).c_str(), padDisp("答案", 6).c_str());
    for (size_t i = 0; i < rows.size(); i++)
        printf("%s  %s  %s  %s  %s  %s\n",
               padDisp(rows[i].name, 14).c_str(), padDisp(rows[i].note, 24).c_str(),
               padDisp(to_string(steps[i]), 14).c_str(), padDisp(to_string(most[i]), 10).c_str(),
               padDisp(to_string(deep[i]), 10).c_str(),
               padDisp(ans[i] == gold ? "同正解" : "✗ 不同", 6).c_str());

    printf("\n★ 八种写法的答案");
    bool allSame = true;
    for (auto& a : ans) allSame &= (a == gold);
    printf("%s（正解给的是 %s）\n", allSame ? "**完全一样**" : "有不一样的", gold.c_str());
    printf("  —— 所以这一整张表里的差别，对拍**一个都看不见**。\n");
    printf("★ log2(%d) = %.2f，对照上面 rankOnly 那一行的「最终树高」。\n",
           n, log2((double)max(n, 1)));
    return 0;
}

// 正解 —— 路径压缩 + 按秩合并
//
// ⚠ 并查集的基本操作第 34 章已经讲完了（dsu.cpp 那一小节：find 是「一路往上找祖宗」，
//   unite 是「把两族的**祖宗**接起来」），这一章不再重复讲一遍。
//   这一份要看的是**另外两句话**，它们俩才是这一章的全部内容：
//
//     ① 路径压缩：find 找到祖宗之后，把这一路上的点**全部直接挂到祖宗身上**，下次一步到位；
//     ② 按秩合并：合并时**矮的那棵挂到高的那棵下面**（rk[x] 是 x 这棵树高度的上界）。
//
//   两句加起来，每次操作的**均摊**代价是 O(α(n))。α 是反阿克曼函数，
//   在 n < 2^65536 的范围里 α(n) ≤ 5 —— 所以它「几乎是常数」，但**它不是常数**，
//   而且这个 α 和第 35 章那个「每个元素进出各一次」一样，是**均摊**出来的：
//   单独某一次 find 完全可以很贵，贵的那几次会被后面变便宜的那些摊掉。
//
// ★ 这一章真正要讲的事情在这里：**上面两句话谁都不影响答案，只影响速度。**
//   把 ② 写反、把 ① 写成一句什么都不干的空话，程序照样**每组都给对的答案** ——
//   对拍一轮都抓不到（第 9 步有现场）。要抓它们只能靠计数器（count.cpp）。
//
// find 这里写成**迭代的两趟**（先找到根，再回头把路上的点挂过去）：
// 递归版更短，可在「不压缩」的那份上会爆栈（deep.cpp 是现场，接第 30 章那条）——
// 为了让三条曲线量的是同一件事，这一章统一写迭代版。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> fa, rk;

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);

    if (!(cin >> n >> m)) return 0;
    fa.resize(n + 1);
    rk.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;
    int cnt = n;                               // 连通块个数：一开始每个点自成一块

    string out;
    for (int i = 0; i < m; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        int ra = find(a), rb = find(b);
        if (op == 1) {
            if (ra == rb) continue;            // ⚠ 已经在一族里了，什么都别做（漏了这句，cnt 就错）
            if (rk[ra] > rk[rb]) swap(ra, rb); // ★ 按秩合并：保证 ra 那棵不比 rb 那棵高
            fa[ra] = rb;                       //   矮的挂到高的下面 —— 树高就不会涨
            if (rk[ra] == rk[rb]) rk[rb]++;    //   只有一样高时，接起来才真的高了一层
            cnt--;
        } else {
            out += (ra == rb ? 'Y' : 'N');
            out += '\n';
        }
    }
    out += to_string(cnt);
    out += '\n';

    cout << out;
    return 0;
}