Паросочетание в общем графе: цветки Эдмондса и веса

import random
from collections import deque
from functools import lru_cache


def edmonds(n, sos):                  # наибольшее паросочетание, цветки
    para = [-1] * n

    def dopolnit(koren):
        otec, baza = [-1] * n, list(range(n))
        v_dereve, och = [False] * n, deque([koren])
        v_dereve[koren] = True

        def obshchij_predok(a, b):    # LCA двух вершин в дереве поиска
            byl = [False] * n
            while True:
                a = baza[a]
                byl[a] = True
                if para[a] == -1:
                    break
                a = otec[para[a]]
            while True:
                b = baza[b]
                if byl[b]:
                    return b
                b = otec[para[b]]

        def pometit(v, b, rebenok, cvetok):
            while baza[v] != b:       # идём по цветку к его основанию
                cvetok[baza[v]] = cvetok[baza[para[v]]] = True
                otec[v] = rebenok
                rebenok = para[v]
                v = otec[para[v]]

        while och:
            v = och.popleft()
            for u in sos[v]:
                if baza[v] == baza[u] or para[v] == u:
                    continue
                vneshnyaya = para[u] != -1 and otec[para[u]] != -1
                if u == koren or vneshnyaya:
                    b = obshchij_predok(v, u)   # нечётный цикл - цветок
                    cvetok = [False] * n
                    pometit(v, b, u, cvetok)
                    pometit(u, b, v, cvetok)
                    for x in range(n):        # сжать цветок в основание
                        if cvetok[baza[x]]:
                            baza[x] = b
                            if not v_dereve[x]:
                                v_dereve[x] = True
                                och.append(x)
                elif otec[u] == -1:
                    otec[u] = v
                    if para[u] == -1:         # свободная - путь найден
                        while u != -1:
                            pv = para[otec[u]]
                            para[u], para[otec[u]] = otec[u], u
                            u = pv
                        return True
                    v_dereve[para[u]] = True
                    och.append(para[u])
        return False

    return sum(dopolnit(v) for v in range(n) if para[v] == -1)


def bez_cvetkov(n, sos):              # «как в двудольном»: обход без
    para, razmer = [-1] * n, 0        # сжатия нечётных циклов
    for koren in range(n):
        if para[koren] != -1:
            continue
        otec, och = {koren: None}, deque([koren])
        while och:
            v = och.popleft()
            for u in sos[v]:
                if u in otec or para[v] == u:
                    continue
                otec[u] = v
                if para[u] == -1:
                    while u is not None:
                        pv = para[otec[u]]
                        para[u], para[otec[u]] = otec[u], u
                        u = pv if pv != -1 else None
                    razmer += 1
                    och.clear()
                    break
                otec[para[u]] = u
                och.append(para[u])
    return razmer


def perebor(n, ves):                  # точный ответ динамикой по маскам
    @lru_cache(None)
    def f(maska):
        v = next((v for v in range(n) if not maska >> v & 1), None)
        if v is None:
            return 0
        luchshe = f(maska | 1 << v)   # v остаётся без пары
        for u in range(n):
            if not maska >> u & 1 and (v, u) in ves:
                luchshe = max(luchshe,
                              ves[v, u] + f(maska | 1 << v | 1 << u))
        return luchshe
    return f(0)


def zhadno(ves):                      # самое тяжёлое ребро первым
    zanyato, itog = set(), 0
    for (u, v), w in sorted(ves.items(), key=lambda x: -x[1]):
        if u not in zanyato and v not in zanyato:
            zanyato |= {u, v}
            itog += w
    return itog


def graf(n, rebra):
    sos = [[] for _ in range(n)]
    for u, v in rebra:
        sos[u].append(v)
        sos[v].append(u)
    return sos


rebra = [(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 4), (2, 5)]
print("граф с циклом 0-2-4-1-3: Эдмондс", edmonds(6, graf(6, rebra)),
      " без цветков", bez_cvetkov(6, graf(6, rebra)))

rng = random.Random(21)
oshibok, hudshee = 0, 1.0
for opyt in range(300):
    n = 14
    rebra = [(u, v) for u in range(n) for v in range(u + 1, n)
             if rng.random() < 0.2]
    edin, ves = {}, {}
    for u, v in rebra:
        edin[u, v] = edin[v, u] = 1
        ves[u, v] = ves[v, u] = rng.randint(1, 100)
    tochno = perebor(n, edin)
    assert edmonds(n, graf(n, rebra)) == tochno
    oshibok += bez_cvetkov(n, graf(n, rebra)) < tochno
    if ves:
        hudshee = min(hudshee, zhadno(ves) / perebor(n, ves))
print("300 графов: Эдмондс совпал с перебором всегда,",
      "без цветков ошибся", oshibok, "раз")
print(f"веса: жадность в худшем случае {hudshee:.2f} от оптимума")