图论算法全解析（五）：二分图、桥与割点、带权并查集与全系列总结

from typing import List
from collections import deque

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color: List[int] = [-1] * n          # -1 = 未染色, 0/1 = 两种颜色

        for start in range(n):
            if color[start] != -1:
                continue

            color[start] = 0
            q: deque[int] = deque([start])

            while q:
                u = q.popleft()
                for v in graph[u]:
                    if color[v] == -1:        # 未染色 → 染相反色
                        color[v] = color[u] ^ 1
                        q.append(v)
                    elif color[v] == color[u]:  # 同色相邻 → 不是二分图
                        return False

        return True

from typing import List, Dict

class Solution:
    def criticalConnections(self, n: int,
                            connections: List[List[int]]) -> List[List[int]]:
        # 建无向图
        graph: Dict[int, List[int]] = {i: [] for i in range(n)}
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)

        dfn: List[int] = [-1] * n
        low: List[int] = [-1] * n
        bridges: List[List[int]] = []
        time = 0

        def dfs(u: int, parent: int) -> None:
            nonlocal time
            dfn[u] = low[u] = time
            time += 1

            for v in graph[u]:
                if v == parent:
                    continue                  # 不往回走到父节点
                if dfn[v] == -1:              # 未访问 → 树边
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    if low[v] > dfn[u]:       # 桥的判定条件
                        bridges.append([u, v])
                else:                         # 已访问 → 回边
                    low[u] = min(low[u], dfn[v])

        dfs(0, -1)
        return bridges

from typing import List, Dict

class WeightedUnionFind:
    def __init__(self):
        self.parent: Dict[str, str] = {}
        self.weight: Dict[str, float] = {}  # weight[x] = x / parent[x]

    def find(self, x: str) -> str:
        if x not in self.parent:
            self.parent[x] = x
            self.weight[x] = 1.0
        if self.parent[x] != x:
            root = self.find(self.parent[x])
            # 路径压缩的同时更新权重
            self.weight[x] *= self.weight[self.parent[x]]
            self.parent[x] = root
        return self.parent[x]

    def union(self, a: str, b: str, value: float) -> None:
        """a / b = value"""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        # 将 ra 挂到 rb 下
        # weight[a] = a / ra, weight[b] = b / rb
        # 需要: weight[ra] = ra / rb
        # ra / rb = (a / rb) / (a / ra)
        #         = (value * b / rb) / weight[a]
        #         = value * weight[b] / weight[a]
        self.parent[ra] = rb
        self.weight[ra] = value * self.weight[b] / self.weight[a]

    def query(self, a: str, b: str) -> float:
        if a not in self.parent or b not in self.parent:
            return -1.0
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            return -1.0
        return self.weight[a] / self.weight[b]


class Solution:
    def calcEquation(self, equations: List[List[str]],
                     values: List[float],
                     queries: List[List[str]]) -> List[float]:
        uf = WeightedUnionFind()
        for (a, b), val in zip(equations, values):
            uf.union(a, b, val)

        return [uf.query(a, b) for a, b in queries]