行列木定理
(Graph/SpanningTree/MatrixTreeTheorem.py)

• View this file on GitHub
• Last update: 2021-05-08 15:33:29+09:00

概要

全域木の通り数を求めるアルゴリズム。行列木定理「無向グラフ $G$ の全域木の通り数は、$G$ のラプラシアン行列の任意の余因子に等しい」を用いて求める。

使い方

MatrixTreeTheorem(n: int)
頂点数 n の空グラフを構築 (ラプラシアン行列を初期化) する。計算量 $O(N^2)$

• add_edge(u, v) -> None
  頂点 u と頂点 v 間に辺を追加する。計算量 $O(1)$

• count_st(MOD: int) -> None
  全域木の通り数を MOD で割った余りを返す。計算量 $O(N^3)$

Code

class MatrixTreeTheorem:
    def __init__(self, n):
        self.n = n
        self.lap_mat = [[0] * n for i in range(n)]

    def _determinant(self, mat, MOD):
        n = len(mat)
        det, rank = 1, 0
        for col in range(n):
            pivot = -1
            for row in range(col, n):
                if mat[row][col] != 0:
                    pivot = row
                    break
            if pivot == -1:
                return 0
            if pivot != rank:
                mat[rank], mat[pivot] = mat[pivot], mat[rank]
                det *= -1
            det *= mat[rank][rank]
            det %= MOD
            inv = pow(mat[rank][rank], MOD - 2, MOD)
            for col2 in range(col, n):
                mat[rank][col2] = mat[rank][col2] * inv % MOD
            for row in range(rank + 1, n):
                fac = mat[row][col]
                for col2 in range(col, n):
                    mat[row][col2] -= mat[rank][col2] * fac
                    mat[row][col2] %= MOD
            rank += 1
        return det

    def add_edge(self, u, v):
        self.lap_mat[u][u] += 1
        self.lap_mat[v][v] += 1
        self.lap_mat[u][v] -= 1
        self.lap_mat[v][u] -= 1

    def count_st(self, MOD):
        mat = [[val for val in rows[:-1]] for rows in self.lap_mat[:-1]]
        return self._determinant(mat, MOD)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page