日々drdrする人のメモ

今日もdrdr、明日もdrdr

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