Pythonで隣接ペアから元の配列を復元するアルゴリズムを解説

問題の概要

サイズ n-1 の2次元配列 adPair が与えられているとします。各 adPair[i] は2つの要素 [ui, vi] を持ち、これは配列 nums において ui と vi が隣接していることを表しています。nums には n 個のユニークな要素が含まれており、この隣接情報だけをもとに元の配列 nums を復元するのが目標です。解が複数存在する場合は、そのうちのどれか1つを返せば構いません。

例えば、入力が adPair = [[3,2],[4,5],[4,3]] の場合、出力は [2, 3, 4, 5] となります。

解決のアプローチ

この問題はグラフの考え方を使うと分かりやすくなります。隣接する要素同士を「辺」で結んだグラフを想像すると、端点(隣接相手が1つしかない要素)が必ず2つ存在し、そこから順にたどっていくことで配列全体を復元できます。

具体的には、以下の手順で解くことができます。

• 隣接リストを作成する: 各ペア (a, b) について、a の隣接リストに b を追加し、b の隣接リストに a を追加します。
• 始点を見つける: 隣接リストの長さが1(つまり隣接相手が1つだけ)のキーを探します。これが配列の端の要素です。見つかったら、[a, l[0]] を初期の nums として設定します。
• 順に復元する: nums の末尾の要素の隣接リストを取得し、その中で「nums の末尾から2番目の要素」と一致しない方を次の要素として追加します。これを adPair のサイズぶん繰り返します。
• 最終的にできあがった nums を返します。

実装例

それでは、実際のコードを見てみましょう。

from collections import defaultdict

def solve(adPair):
    my_map = defaultdict(list)
    for a, b in adPair:
        my_map[a].append(b)
        my_map[b].append(a)

    for a, l in my_map.items():
        if len(l) == 1:
            nums = [a, l[0]]
            break
    for i in range(1, len(adPair)):
        a, b = my_map[nums[-1]]

        if a == nums[-2]:
            nums.append(b)
        else:
            nums.append(a)

    return nums

adPair = [[3,2],[4,5],[4,3]]
print(solve(adPair))

入力

[[3,2],[4,5],[4,3]]

出力

[2, 3, 4, 5]

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。隣接リストの構築に各ペアを1度ずつ処理し、復元フェーズでも各要素を1度ずつ追加するため、非常に効率的な手法といえます。