Pythonでフォロー関係リストから相互フォロワーを見つける方法

問題の概要

「relations」というリストがあると仮定します。このリストの各要素 relations[i] は2つの数値 [ai, bi] からなり、ソーシャルメディア上で「人物 ai が人物 bi をフォローしている」ことを表しています。ここで、互いにフォローし合っている人々（相互フォロワー）の一覧を求め、昇順にソートして返す必要があります。

たとえば、入力が relations = [[0, 2], [2, 3], [2, 0], [1, 0]] の場合、出力は [0, 2] となります。

解決のための手順

この問題は、次の手順で解くことができます。

• 空のセット ans と seen を用意します。
• relations 内の各ペア (a, b) に対して、以下を繰り返します。
  • ペア (a, b) を seen に記録します。
  • 逆のペア (b, a) がすでに seen に存在する場合は、a と b を ans に追加します。
• 最後に ans の要素をソートして返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(relations):
    ans = set()
    seen = set()

    for a, b in relations:
        seen.add((a, b))

        if (b, a) in seen:
            ans.add(b)
            ans.add(a)

    k = list(ans)
    rtr = sorted(k)
    return rtr

relations = [
   [0, 2],
   [2, 3],
   [2, 0],
   [1, 0]
]
print(solve(relations))

入力

[[0, 2],[2, 3],[2, 0],[1, 0]]

出力

[0, 2]

アルゴリズムのポイント

このアルゴリズムでは、セット（set）を活用することで高速な存在確認を実現しています。ペア (a, b) を登録する際に、その逆向きのペア (b, a) がすでに登録されているかどうかをチェックすれば、相互フォローの関係を効率的に検出できます。セットへの追加や検索は平均 O(1) で行え、最終的なソートが O(n log n) となるため、データ量が多くても十分に実用的な速度で動作します。