【Python】全員が少なくとも1人の友達を持っているかどうかを確認するプログラムの作り方

問題の概要

0からn-1までの番号で表されるn人の人がいるとします。また、友人関係を表すタプルのリストfriendsが与えられ、friends[i][0]とfriends[i][1]は互いに友人であることを示しています。このとき、全員が少なくとも1人の友人を持っているかどうかを判定するプログラムを作成します。

具体例

例えば、入力が n = 3、friends = [[0, 1], [1, 2]] の場合、出力はTrueになります。その理由は以下の通りです。

• 人0は人1と友人である
• 人1は人0と人2の両方と友人である
• 人2は人1と友人である

このように全員が少なくとも1人の友人を持っているため、結果はTrueとなります。

解決のアプローチ

この問題は、各人が友人を持っているかどうかを記録するフラグ配列を使うことで、シンプルに解決できます。手順は以下の通りです。

1. サイズnのリストpeopleを作成し、すべて0（False）で初期化します。
2. friendsリスト内の各友人関係（リンク）について、関係する2人のインデックスに対応するpeopleの要素をTrueに設定します。
3. peopleリスト内のすべての要素を確認し、Falseのまま残っている要素（つまり誰とも友人ではない人）が存在すればFalseを返します。
4. すべての要素がTrueであれば、全員が少なくとも1人の友人を持っていることになるのでTrueを返します。

実装例

class Solution:
    def solve(self, n, friends):
        people = [0 for i in range(n)]
        for link in friends:
            people[link[0]] = True
            people[link[1]] = True
        for person in people:
            if not person:
                return False
        return True

ob = Solution()
n = 3
friends = [ [0, 1], [1, 2] ]
print(ob.solve(n, friends))

入力

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

出力

True

計算量について

このアルゴリズムの時間計算量はO(n + m)です。ここで、nは人数、mは友人関係の数を表します。各友人関係を一度ずつ処理した後、全員分のフラグを確認するためです。空間計算量はO(n)となり、各人の友人の有無を記録するためのリストが必要になります。

この手法はグラフ理論における「孤立ノードの検出」と考えることもできます。人をノード、友人関係をエッジとみなした場合、どのエッジにも接続されていないノードが存在するかどうかを効率的に判定できるのがポイントです。