SRM733 Div1 Medium: BuildingSpanningTreesDiv1 - 日々ｄｒｄｒする人のメモ

TopCoder SRM 733のMedium "BuildingSpanningTreesDiv1"

解法メモ

N個の頂点を持つ完全グラフ ${G}$ において、このグラフに含まれる辺の部分集合 ${E}$ が与えられる。グラフ ${G}$ の部分グラフに、集合 ${E}$ の辺を全て含む全域木がいくつ存在するか(各頂点は区別する)を計算する問題。

定式化しようと思ったけど手が出なかった。

公式の解説: Single Round Match 733 Editorials -

解法は、

集合 ${E}$ の辺で閉路が形成されないかをチェックし、閉路が存在すれば0を出力。
集合 ${E}$ から形成された森において、各木の頂点数 ${s_i}$ を計算し、 ${N^{k-2} * s_0 * \dots * s_{k-1}}$ (kは森に含まれる木の数)を出力。
計算量は ${O(n * \alpha(n))}$ ( ${\alpha}$ はアッカーマン関数の逆関数)

完全グラフに含まれる全域木の個数に関してCayley's formulaが存在し、頂点がN個の場合は ${N^{N-2}}$ となる。

この問題ではCaley's formulaを一般化した以下の式を利用する。
${\sum_T s_0^{d_0}s_1^{d_1} \dots s_{k-1}^{d_{k-1}} = s_0 s_1 \dots s_{k-1} (s_0 + s_1 + \dots + s_{k-1})^{k-2}}$

この問題の森において、どの木と木を繋ぐかが決まった時、それぞれの木同士を繋ぎ方は ${s_0^{d_0}s_1^{d_1} \dots s_{k-1}^{d_{k-1}}}$ 通りであることがわかるため、右辺に変形できれば解が計算できる。

一般化したCayley's formulaの参考:
combinatorics - Proof of Generalized Cayley's formula - Mathematics Stack Exchange

参考先のページでは、以下の式を示している。
${\sum_T x_0^{d_0-1}x_1^{d_1-1} \dots x_{n-1}^{d_{n-1}-1} = (x_0 + x_1 + \dots + x_{n-1})^{n-2}}$

(特に ${x_i}$ がなんだろうと思って)この式の意味の解釈に少し悩んだ。この式は任意の ${x_0, \dots, x_{n-1}}$ について成り立つ。
左辺の式では、n個の頂点からなる各木 ${T}$ のPrüfer sequenceに対し、各頂点ラベルiが出現した分だけ(つまり ${d_i-1}$ 回) ${x_i}$ 掛けた値を計算し、全ての木におけるその積の和を計算している。
ここで、Prüfer sequenceは長さn-2のラベル1~nからなる全ての組み合わせ(つまり ${n^{n-2}}$ 通り)が存在するため、右辺のように ${x_0, \dots, x_{n-1}}$ の全ての出現順の積の和になることがわかる。

解法コード (Python2)

class BuildingSpanningTreesDiv1:
    def getNumberOfSpanningTrees(self, n, x, y):
        p = range(n)
        def root(x):
            if x == p[x]:
                return x
            p[x] = y = root(p[x])
            return y
        def unite(x, y):
            px = root(x); py = root(y)
            if px == py:
                return 0
            if px < py:
                p[py] = px
            else:
                p[px] = py
            return 1
        for s, t in zip(x, y):
            if not unite(s-1, t-1):
                return 0

        g = [0]*n
        k = 0
        for i in range(n):
            j = root(i)
            if i == j:
                k += 1
            g[j] += 1
        if k == 1:
            return 1
        MOD = 987654323
        ans = pow(n, k-2, MOD)
        for i in range(n):
            if g[i]:
                ans = (ans * g[i]) % MOD
        return ans