Pythonでグラフがすべての人にとって移動可能かどうかを確認するプログラム

n個の頂点（0からn-1までの番号が付けられたもの）から構成される無向グラフが与えられます。各辺には重みが設定されており、重みは「1」「2」「3」の3種類があります。このグラフを移動できるのはJackとCaseyの2人で、Jackは重み1の辺のみ、Caseyは重み2の辺のみを移動でき、重み3の辺は両方が移動できます。

ここで、JackとCaseyの両方がグラフ内のすべての頂点に到達できるようにするために、不要な辺を削除することを考えます。このとき削除が必要な辺の本数を求め、どのようにしても移動可能な状態にできない場合は-1を返します。

例えば、入力が次のような場合を考えてみましょう。

n = 5 の場合、出力は -1 になります。このグラフは、辺をいくら削除してもJackとCaseyの両方にとって移動可能な状態にすることができないためです。

解法のアプローチ

この問題は、Union-Find（素集合データ構造）を使うことで効率的に解くことができます。ポイントは、まず両方が利用できる重み3の辺を優先的に処理し、その後Jack用・Casey用のグラフをそれぞれ独立に構築することです。

なお、各辺は (u, v, w) の形式で与えられるものとし、u は辺の種類（1＝Jack専用、2＝Casey専用、3＝両方が使用可能）、v と w はその辺で接続される2つの頂点を表します。具体的な手順は以下の通りです。

• 関数 find() を定義します。引数は val です。

  • val が root[val] と等しくない場合、root[val] := find(root[val]) とします（経路圧縮）。

  • root[val] を返します。

• 関数 union() を定義します。引数は val1 と val2 です。

  • val1 := find(val1)、val2 := find(val2) とします。

  • val1 と val2 が等しい場合（すでに同じ連結成分に属している場合）は 0 を返します。

  • root[val1] := val2 とし、1 を返します。

• res := 0、edge1 := 0、edge2 := 0 と初期化します。

• root := 0 から n + 1 までの範囲からなる新しいリストを作成します。

• e 内の各辺 (u, v) とその重み w について、次の処理を行います。

  • u が 3 と等しい場合（両方が通れる辺の場合）：

    • union(v, w) の結果が 0 以外であれば、edge1 := edge1 + 1、edge2 := edge2 + 1 とします。

    • それ以外の場合（冗長な辺の場合）は、res := res + 1 とします。

• root0 := root[0:] として、現時点の root のコピーを保存します。

• 再び e 内の各辺 (u, v) と重み w について、次の処理を行います。

  • u が 1 と等しい場合（Jack専用の辺の場合）：

    • union(v, w) の結果が 0 以外であれば、edge1 := edge1 + 1 とします。

    • それ以外の場合は、res := res + 1 とします。

• root := root0 として、root を元の状態に戻します。

• さらに e 内の各辺 (u, v) と重み w について、次の処理を行います。

  • u が 2 と等しい場合（Casey専用の辺の場合）：

    • union(v, w) の結果が 0 以外であれば、edge2 := edge2 + 1 とします。

    • それ以外の場合は、res := res + 1 とします。

• edge1 と edge2 がどちらも n - 1 と等しい場合は res を返します。

• それ以外の場合は -1 を返します。

ここで res は「削除しても連結性に影響しない冗長な辺」の数を表しています。また、edge1 と edge2 がそれぞれ n - 1（全域木に必要な辺の本数）に達していれば、JackとCaseyの両方がグラフ全体を移動できることが保証されます。

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(n, e):
    def find(val):
        if val != root[val]:
            root[val] = find(root[val])
        return root[val]
    def union(val1, val2):
        val1, val2 = find(val1), find(val2)
        if val1 == val2: return 0
        root[val1] = val2
        return 1
    res = edge1 = edge2 = 0
    root = list(range(n + 1))
    for u, v, w in e:
        if u == 3:
            if union(v, w):
                edge1 += 1
                edge2 += 1
            else:
                res += 1
    root0 = root[:]
    for u, v, w in e:
        if u == 1:
            if union(v, w):
                edge1 += 1
            else:
                res += 1
    root = root0
    for u, v, w in e:
        if u == 2:
            if union(v, w):
                edge2 += 1
            else:
                res += 1
    return res if edge1 == edge2 == n - 1 else -1
print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))

入力

5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]

出力

-1