洛谷 P1551 亲戚

// P1551 亲戚 —— ★ 这一版就能 AC
//
// 最裸的连通性查询：给 m 条「是亲戚」的关系，问 p 对人是不是亲戚。
// 题单里它的定位是「**用它确认你默写的版本是对的**」——
// ⚠ 而这一页真正想说清楚的是另一件事：**这道题其实用不着并查集**（第 ② 步），
//   那么「什么时候非它不可」？答案在第 ③ 步。
//
// ⚠ 输出是 `Yes` / `No`（首字母大写）—— 隔壁 [P3367](/sol/p3367/) 要的是单字母 `Y` / `N`。
#include <bits/stdc++.h>
using namespace std;

static const int N = 5005;
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 n, m, p;
    if (!(cin >> n >> m >> p)) return 0;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        fa[find(a)] = find(b);
    }
    string out;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        out += (find(a) == find(b)) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

// P1551 · 另一条正确的路：建图 + 一次 BFS 把每个连通块染上颜色
//
// ★ 它和并查集一行代码都不共享：把 m 条关系当成无向边建图，从每个没染色的点出发 BFS 一遍，
//   同色即亲戚。复杂度 O(n + m)，比并查集还直白。
//
// ⚠⚠ 但它有一个**结构上的前提**：**所有的边必须先读完**。
//   这道题恰好是「先给全部关系、再给全部询问」——**离线**的，所以它成立。
//   ⇒ 一旦合并和询问**交错**出现（比如 [P3367](/sol/p3367/) 那种格式），
//     它就得每来一个询问重染一次 —— 那才是并查集不可替代的地方（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 5005;
static vector<int> g[N];
static int col[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, p;
    if (!(cin >> n >> m >> p)) return 0;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) col[i] = 0;
    int c = 0;
    for (int s = 1; s <= n; s++) {
        if (col[s]) continue;
        col[s] = ++c;
        vector<int> q{s};
        for (size_t h = 0; h < q.size(); h++) {
            int u = q[h];
            for (int v : g[u]) if (!col[v]) { col[v] = c; q.push_back(v); }
        }
    }
    string out;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        out += (col[a] == col[b]) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

// P1551 · 错法 ①：合并时**没有先找根** —— 直接 fa[a] = b
//
//   fa[find(a)] = find(b);   ← 正解：把 a 的**祖宗**挂到 b 的**祖宗**下面
//   fa[a] = b;               ← 这一版：把 a 自己挂过去
//
// ⚠ 它把 a 原来的父亲**弄丢了** —— a 底下那一整棵子树就此和 a 的老家断开。
// ★ 这是初学者最常写出来的一发 WA，而且**对拍抓得到**（和本章第 11 步那五种正好相反）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 5005;
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 n, m, p;
    if (!(cin >> n >> m >> p)) return 0;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        fa[a] = b;                          // ✗ 没先找根
    }
    string out;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        out += (find(a) == find(b)) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}