带权并查集

• 概述

带权并查集是并查集在合并时，增加一个权值数组，对于不同的问题，权值数组定义的方式是不同的，读者可以通过几道例题来体会。

• 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
分析：

参考解答：
深度优先遍历

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = collections.defaultdict(set)
        for i in range(len(equations)):
            f, s = equations[i]
            graph[f].add((s, values[i]))
            graph[s].add((f, 1/values[i]))
        ret = []
        def dfs(cur, target, visited, result=1.0):
            if cur == target:
                return (True, result)
            visited.add(cur)
            for adj, v in graph[cur]:
                if adj not in visited:
                    res = dfs(adj, target, visited)
                    if res[0]:
                        return (True, res[1] * v)
            return (False, -1.0)
        for q in queries:
            result = 1.0
            if q[0] not in graph or q[1] not in graph:
                ret.append(-1.0)
            elif q[0] == q[1]:
                ret.append(1.0)
            else:
                ret.append(dfs(q[0], q[1], set())[1])
        return ret

带权并查集

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        f, w = dict(), dict()
        def find(p):
            f.setdefault(p, p)
            w.setdefault(p, 1.0)
            if p != f[p]:
                fp = find(f[p]) # 更新顺序不可简写，不可颠倒
                w[p] *= w[f[p]]
                f[p] = fp
            return f[p]
        def union(p, q, k):
            pRoot = find(p)
            qRoot = find(q)
            f[pRoot] = qRoot
            w[pRoot] = k * w[q] / w[p]

        for (a, b), v in zip(equations, values):
            union(a, b, v)
        return [w[a] / w[b] if a in f and b in f and find(a) == find(b) else -1.0 for a, b in queries]

floyed算法

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        var = set()
        graph = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v
            graph[b][a] = 1 / v
            var.add(a)
            var.add(b)
        for k in var:
            for i in var:
                for j in var:
                    if k in graph[i] and j in graph[k]:
                        graph[i][j] = graph[i][k] * graph[k][j]
        return [graph[a][b] if a in var and b in var and b in graph[a] else -1.0 for a, b in queries]

• 矛盾区间和

给定一系列区间和，区间和的对应值为, 依照区间和给出的先后顺序，判断哪些区间和是互相矛盾的。即，最先给出的区间和，我们认为是合理的，后续给出的一些区间和可能存在一些矛盾，记录一共有多少矛盾的区间和。
分析：
题目中给的区间为双闭区间，为了保证区间可相加，方便合并，我们将区间定义为前开后闭，具体做法则是将左边界值减一。

• 食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
分析：
用3个数字0、1、2来表示3种关系，同类、吃、被吃。
路径压缩时，假如子、父、祖为x、y、z，即x原先的父亲为y，y经过路径压缩后的父亲为z，x经过路径压缩之后也会指向z。

def find(p):
    if f[p] != p:
        ancestor = find(f[p])
        w[p] = (w[p] + w[f[p]]) % 3
        f[p] = ancestor
    return f[p]

判断是否有冲突：
假如两个动物已经相连，说明两个动物的祖先节点相同。

def union(p, q):
    ans = 0  # ans只记录矛盾导致的假话
    pRoot = find(p)
    qRoot = find(q)
    if pRoot == qRoot and (w[p] - w[q] + 3) % 3 != d - 1:  # 同类时d=1，p吃q时d=2
        ans += 1
    elif pRoot != qRoot:
        f[pRoot] = qRoot
        w[pRoot] = (d-1 + w[q] - w[p] + 3) % 3