算法 - 亲戚关系

清疚 2023-09-23 13:06 61阅读 0赞

**目录**

题目描述

输入描述

输出描述

用例

题目分析

算法源码

--------------------

### 题目描述 ###

现在有若干家族图谱关系，给出了一些亲戚关系，如 A 和 B 是亲戚，B 和 C 是亲戚，那么 A和 B 也是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

### 输入描述 ###

第一部分是以 N，M 开始。N 为人数（1 <= N <= 20000），这些人的编号为 1，2，3，…，N。下面有 M行（1 <= M <= 1000000），每行有两个数 a，b，表示 a 和 b 是亲戚。

第二部分是以 Q 开始。以下 Q 行有 Q 行询问（1 <= Q <= 1000000），每行为 c, d, 表示询问 c 和 d 是否为亲戚。

### 输出描述 ###

对于询问 c, d, 输出一行：若 c, d 为亲戚，则输出“YES”，否则输出“NO”。

### 用例 ###

### 题目分析 ###

本题是典型的连通图求解问题，可以使用并查集解决。

和下面题目类似

[华为机试 - 发广播\_伏城之外的博客-CSDN博客][- _-CSDN]

我们可以通过上面题目了解并查集结构的定义，以及合并、查找功能的实现。

本题，相较于上面的题目反而更简单，更易于理解一点。

只是本题的输入处理比较麻烦一点。

### 算法源码 ###

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    const lines = [];
    let n;
    let m;
    let ufs;
    let q;
    rl.on("line", (line) => {
      lines.push(line);
    
      if (lines.length === 1) {
        [n, m] = lines[0].split(" ").map(Number);
        ufs = new UnionFindSet(n);
        return;
      }
    
      if (m && lines.length === m + 1) {
        for (let i = 1; i < lines.length; i++) {
          let [p1, p2] = lines[i].split(" ");
          ufs.union(p1 - 1, p2 - 1);
        }
        return;
      }
    
      if (m && lines.length === m + 2) {
        q = parseInt(lines[lines.length - 1]);
        return;
      }
    
      if (m && q && lines.length === m + 2 + q) {
        for (let i = m + 2; i < lines.length; i++) {
          let [p1, p2] = lines[i].split(" ");
          if (ufs.find(p1 - 1) === ufs.find(p2 - 1)) {
            console.log("YES");
          } else {
            console.log("NO");
          }
        }
        lines.length = 0;
        return;
      }
    });
    
    class UnionFindSet {
      constructor(n) {
        this.fa = [];
        this.init(n);
      }
    
      init(n) {
        for (let i = 0; i < n; i++) this.fa[i] = i;
      }
    
      find(x) {
        if (x !== this.fa[x]) {
          this.fa[x] = this.find(this.fa[x]);
          return this.fa[x];
        }
        return x;
      }
    
      union(x, y) {
        let x_fa = this.find(x);
        let y_fa = this.find(y);
        if (x_fa !== y_fa) {
          this.fa[y_fa] = x_fa;
        }
      }
    }

[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127588130?spm=1001.2014.3001.5502