P1551.亲戚

原题链接
image.png

思路

  • 并查集可以参考这条链接，写得非常好。https://zhuanlan.zhihu.com/p/93647900
  • 所谓并查集，本质上就是3步走
    1. init操作，初始化集合，确定每个元素的父亲节点就是自己，同时，每个节点的秩（深度）都是1
    2. find操作，也就是“查”，找到父亲节点，并使得树的层次尽可能少，尽可能扁平。
    3. merge操作，也就是“并”，“查”是“并”的基础。按秩（就是深度）的大小进行合并的操作。
  • init进行初始化，确定每个元素的父亲节点就是自己，同时秩（深度）为1。 ```cpp int fa[maxN]; int rank[maxN];

void init(n) { for (int i = 0; i < n; ++i) { fa[i] = i; rank[i] = 1; } }

  2. - `find`的意义在于可以找到每个节点的父亲节点是谁，同时，改变结构关系，使得树的层次尽可能浅。
  3. ```cpp
  4. // find
  5. void find(int x) {
  6.     if (fa[x] == x) {
  7.         return fa[x];
  8.     } else {
  9.         fa[x] = find(fa[x]);
  10.         return fa[x];
  11.     }
  12. }

  • merge操作的意义有两点。第一，完成合并，第二，小层次的树挂到大层次的树上面，这样搞可以使得整体的层次更小。

    1. // merge
    2. void merge(int x, int y) {
    3.   int fa_x = find(x), fa_y = find(y);
    4.   if (rank[fa_x] <= rank[fa_y]) {
    5.       fa[fa_x] = fa_y;
    6.   } else {
    7.       fa[fa_y] = fa_x;
    8.   }
    10.   // 如果层次一样，需要 + 1
    11.   if (rank[fa_x] == rank[fa_y] && fa_x != fa_y)
    12.       rank[fa_y]++;
    13. }

    代码

    ```cpp

    include

    include

using namespace std;

const int maxn = 5000 + 5;

int fa[maxn], r[maxn];

void init(int n) { for (int i = 0; i < n; i++) { fa[i] = i; r[i] = 1; } }

int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }

void merge(int i, int j) { int x = find(i), y = find(j); if (r[x] <= r[y]) { fa[x] = y; } else { fa[y] = x; }

if (r[x] == r[y] && x != y) {
    r[y]++;
}

}

int main() { int n, m, p, x, y; scanf(“%d%d%d”, &n, &m, &p); init(n); for (int i = 0; i < m; i++) { scanf(“%d%d”, &x, &y); merge(x, y); }

for (int i = 0; i < p; i++) {
    scanf("%d%d", &x, &y);
    printf("%s\n", find(x) == find(y) ? "Yes" : "No");
}

return 0;

} ```