Day55-图论，卡码网107

并查集

• 并查集常用来解决连通性问题，如判断两个元素是否在同一个集合里

• 并查集的功能

  • 寻找根节点，函数：find(u)，即判断这个节点的祖先节点是哪个
  • 将两个节点添加到同一个集合，函数：join(u, v)，将两个节点连在同一个根节点上
  • 判断两个节点是否在同一个集合，函数：isSame(u, v)，即判断两个节点是不是同一个根节点

• 原理

  • 初始化，每个元素自成一集合，father[i]=i
  • 查找操作，寻根，判断是否是同一个根，根相同则说明在一个集合里
  • 合并操作，将v->u这条边加入并查集

// 并查集 代码模板
/**
 * 1. 构造函数：
    初始化时每个节点的父节点指向自己
    JavaScript 使用类(class)封装并查集逻辑
 * 2. find 方法：
    递归查找根节点
    包含路径压缩优化，将查找路径上的节点直接指向根
 * 3. isSame 方法：
    判断两个节点是否属于同一集合
    通过比较它们的根节点实现
 * 4. join 方法：
    合并两个节点所在的集合
    将其中一个集合的根指向另一个集合的根
 */
class joinFind {
  constructor(size) {
    // 初始化父节点数组，每个节点的父节点指向自己
    this.father = new Array(size);
    for (let i = 0; i < size; i++) {
      this.father[i] = i;
    }
  }

  /**
   * 查找节点的根（带路径压缩）
   * @param {number} u 节点
   * @returns {number} 根节点
   */
  find(u) {
    if (this.father[u] === u) return u;
    // 路径压缩：将查找路径上的节点直接指向根
    this.father[u] = this.find(this.father[u])
    return this.father[u]
  }

  /**
   * 判断两个节点是否属于同一集合
   * @param {number} u 节点1
   * @param {number} v 节点2
   * @returns {boolean} 是否同一集合
   */
  isSame(u, v) {
    u = this.find(u)
    v = this.find(v)
    if (u == v) return true
    return false
    // return this.find(u) === this.find(v);
  }

  /**
   * 合并两个节点所在的集合
   * @param {number} u 节点1
   * @param {number} v 节点2
   */
  join(u, v) {
    const rootU = this.find(u);
    const rootV = this.find(v);
    if (rootU === rootV) return; // 已在同一集合
    this.father[rootV] = rootU; // 将v的根指向u的根
  }
}

// 使用示例
const n = 1005; // 根据题目需求设置大小
const uf = new joinFind(n);

// 合并操作示例
uf.join(1, 2);
uf.join(2, 3);

// 查询操作示例
console.log(uf.isSame(1, 3)); // true
console.log(uf.isSame(1, 4)); // false

• 两种优化方式
  • 路径压缩：将查找路径上的所有节点直接指向根，使树更扁平
  • 按秩合并：避免树过高

// 按秩合并的代码
class joinFind {
  constructor(size) {
    this.size = size;
    this.father = new Array(size);
    this.rank = new Array(size);
    
    // 初始化
    for (let i = 0; i < size; i++) {
      this.father[i] = i; // 每个元素的父节点指向自己
      this.rank[i] = 1;   // 初始高度为1
    }
  }

  /**
   * 查找根节点（不带路径压缩）
   * @param {number} u 节点
   * @returns {number} 根节点
   */
  find(u) {
    while (this.father[u] !== u) {
      u = this.father[u];
    }
    return u;
  }

  /**
   * 判断两个节点是否连通
   * @param {number} u 节点1
   * @param {number} v 节点2
   * @returns {boolean} 是否连通
   */
  isSame(u, v) {
    return this.find(u) === this.find(v);
  }

  /**
   * 合并两个节点（按秩合并优化）
   * @param {number} u 节点1
   * @param {number} v 节点2
   */
  join(u, v) {
    let rootU = this.find(u);
    let rootV = this.find(v);
    
    if (rootU === rootV) return; // 已经在同一集合
    
    // 按秩合并：将矮树合并到高树下
    if (this.rank[rootU] <= this.rank[rootV]) {
      this.father[rootU] = rootV;
      // 当两棵树高度相同时，合并后高度+1
      if (this.rank[rootU] === this.rank[rootV]) {
        this.rank[rootV]++;
      }
    } else {
      this.father[rootV] = rootU;
    }
  }
}

// 使用示例
const n = 1005; // 根据题目需求设置大小
const uf = new joinFind(n);

// 合并操作示例
uf.join(1, 2);
uf.join(2, 3);
uf.join(4, 5);

// 查询操作示例
console.log(uf.isSame(1, 3)); // true
console.log(uf.isSame(1, 4)); // false
console.log(uf.isSame(4, 5)); // true

---

---

107. 卡码网-寻找存在的路径

• 题目描述：给定一个包含 n 个节点的无向图中，节点编号从 1 到 n （含 1 和 n ）。你的任务是判断是否有一条从节点 source 出发到节点 destination 的路径存在。

• 输入描述：第一行包含两个正整数 N 和 M，N 代表节点的个数，M 代表边的个数。 后续 M 行，每行两个正整数 s 和 t，代表从节点 s 与节点 t 之间有一条边。 最后一行包含两个正整数，代表起始节点 source 和目标节点 destination。

• 输出描述：输出一个整数，代表是否存在从节点 source 到节点 destination 的路径。如果存在，输出 1；否则，输出 0。

---

• 思路
• 无向图，判断一个节点到另一个节点有没有有效路径即是看这两个节点是否在同一个集合里，有边连在一起就算一个集合
• 并查集

const r1 = require('readline').createInterface({ input: process.stdin });
// 创建readline接口
let iter = r1[Symbol.asyncIterator]();
// 创建异步迭代器
const readline = async () => (await iter.next()).value;


let N, M // 节点数和边数
let source, destination // 起点 终点
let father = []  // 并查集


// 并查集初始化
const init = () => {
  for (let i = 1; i <= N; i++)  father[i] = i;
}

// 并查集里寻根的过程
const find = (u) => {
  return u == father[u] ? u : father[u] = find(father[u])
}

// 将v->u 这条边加入并查集
const join = (u, v) => {
  u = find(u)
  v = find(v)
  if (u == v) return // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
  father[v] = u
}

// 判断 u 和 v是否找到同一个根
const isSame = (u, v) => {
  u = find(u)
  v = find(v)
  return u == v
}


(async function () {
  // 读取第一行输入
  let line = await readline();
  [N, M] = line.split(' ').map(Number);

  // 初始化并查集
  father = new Array(N)
  init()

  // 读取边信息, 加入并查集
  for (let i = 0; i < M; i++) {
    line = await readline()
    line = line.split(' ').map(Number)
    join(line[0], line[1])
  }

  // 读取起点和终点
  line = await readline(); //JS注意这里的冒号
  [source, destination] = line.split(' ').map(Number)

  if (isSame(source, destination)) return console.log(1);
  console.log(0);
})()

---

---

---

参考&感谢各路大神

• 代码随想录
• B站：代码随想录