算法 | 并查集原理和题目练习

一、原理

原理可以查看这个博客，写得很通俗易懂。如果你要看懂下面的代码，最好先看这个博客。
https://blog.csdn.net/qq_41593380/article/details/81146850

二、实际题目

547. 朋友圈

中等题

1. 题目

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

2. 代码
   这道题非常常规的用并查集啦，就是原理中博客的情况，查找图的连通分离数。

var findCircleNum = function(M) {
    const len = M.length
    let total = len
    const pre = Array(len)
    for(let i=0;i<len;i++) pre[i] = i
    const unionSearch = (root) => {
        let son = root
        let tmp
        while(root!==pre[root])
            root=pre[root]
        while(son!==root) {
            tmp = pre[son]
            pre[son] = root
            son = tmp
        }
        return root
    }
    for(let i=0;i<len;i++) {
        for(let j=i+1;j<len;j++) {
            if(M[i][j]===1) {
                let r1 = unionSearch(i)
                let r2 = unionSearch(j)
                if(r1 !== r2) {
                    pre[r1] = r2
                    total--
                }
            }
        }
    }
    return total
};

399. 除法求值

中等题

1. 题目

给出方程式 A / B = k , 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
示例 :
给定：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
返回：[6.0, 0.5, -1.0, 1.0, -1.0 ]
输入：方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

2. 代码
   这道题是一道变形的并查集题目，主要是还包括了边的权（一个节点除以一个节点的值），所以我们拿到题的时候得理解下这个边的大小和方程式的计算有什么联系。
   我们假设边权edge代表是pre[b] / b的值，有两个步骤需要计算edge。
   （1）路径压缩时，也就是unionsearch的时候。
   其实就是在压缩路径的时候顺便给每个节点的edge一路乘到根节点。直接看图。

   
   路径压缩前
   路径压缩后

（2）并集的时候。
可以看代码注释并集的操作。就是当两个节点通过查询发现两者的老大哥不是一个的时候，合并两个集合就是把两个老大哥连起来，此时，我们两个原本要并的节点已经被路径压缩直接连接到他们的老大哥下了，如下图所示，我们要把r2连在r1下面，就是要计算r1 / r2，通过简单的数学计算可以知道：r1 / r2 = edge1 / edge2 * value。

var calcEquation = function(equations, values, queries) {
    // 并查集 + 路径压缩
    const pre = {}
    const len = equations.length
    const res = []
    // pre[b] = {node:a, edge: 2}
    for(let i=0;i<len;i++) {
        // 初始化pre数组，这里的pre数组已经是哈希表了，并且存储还包括edge
        const [n1,n2] = equations[i]
        pre[n1] = {node:n1,edge:1}
        pre[n2] = {node:n2,edge:1}
    }
    
    // 路径压缩
    const unionsearch = (root) => {
        let son
        son = root
        let multi=1
        if(!pre[root]) {
            return -1
        }
        while(root !== pre[root].node) {
            multi *= pre[root].edge
            root = pre[root].node
        }
        let tmpNode, tmpEdge
        while(son !== root) {
            tmpNode = pre[son].node
            tmpEdge = pre[son].edge
            pre[son].node = root
            pre[son].edge = multi
            multi /= tmpEdge
            son = tmpNode
        }
        return root
    }

    // 并集
    for(let i =0;i<len;i++) {
        const [n1,n2] = equations[i]
        let r1 = unionsearch(n1)
        let r2 = unionsearch(n2)
        if(r1 !== r2) {
            pre[r2] = {node:r1, edge:pre[n1].edge*values[i]/pre[n2].edge}
        }
    }

    const qLen = queries.length

    for(let i=0;i<qLen;i++) {
        const [n1,n2] = queries[i]
        let r1 = unionsearch(n1)
        let r2 = unionsearch(n2)

        if(r1 !== r2) {
            res.push(-1)
        } else if(r1 === -1 || r2 === -1) {
            res.push(-1)
        } else {
            res.push(pre[n2].edge/pre[n1].edge)
        }
    }

    return res
};