Pythonで捕食関係を考慮した動物の最小グループ数を求めるアルゴリズム

問題概要

数値のリスト nums が与えられます。nums[i] は i 番目の動物の捕食者を表しており、捕食者が存在しない場合は −1 が格納されています。ここで、「どの動物も、自分の直接・間接の捕食者と同じグループに含まれない」ように動物たちをグループ分けすることを考えます。このとき必要となる最小のグループ数を求めるのが目的です。

たとえば、入力が nums = [1, 2, -1, 4, 5, -1] の場合、出力は 3 になります。これは [0, 3]、[1, 4]、[2, 5] のように 3 つのグループへ分割できるためです。

考え方：捕食関係を木構造として捉える

捕食関係は自然に「木構造」として表現できます。捕食者を持たない動物（値が −1 の要素）が木の根となり、捕食される関係が親子の辺に相当します。同じ深さに位置する動物同士は互いに捕食関係を持たないため、深さごとにグループ化すれば条件を満たすことができます。

つまり、求める最小グループ数は「最も深い木の深さ」と一致します。これを求めるために、各根から深さ優先探索（DFS）を行い、到達できる最大の深さを記録していきます。

アルゴリズムの手順

1. リスト A が空であれば、0 を返します。
2. 隣接リスト adj、訪問済み集合 vis、根のリスト roots を用意します。
3. 各インデックス i と値 a について、a が −1 なら i を根として roots に追加します。また、adj[i] に a を、adj[a] に i を追加して双方向の辺を作ります。
4. best を負の無限大で初期化します。
5. 各根についてスタックを使った DFS を実行し、各ノードの深さ d を追跡しながら best を最大値で更新します。
6. 最後に best を返します。

Pythonでの実装例

from collections import defaultdict

class Solution:
    def solve(self, A):
        if not A:
            return 0
        adj = defaultdict(list)
        vis = set()
        roots = []
        for i, a in enumerate(A):
            if a == -1:
                roots.append(i)
            adj[i].append(a)
            adj[a].append(i)
        best = -float("inf")
        for root in roots:
            stk = [(root, 1)]
            while stk:
                node, d = stk.pop()
                if node in vis or node == -1:
                    continue
                best = max(best, d)
                vis.add(node)
                for u in adj[node]:
                    stk.append((u, d + 1))
        return best

ob = Solution()
nums = [1, 2, -1, 4, 5, -1]
print(ob.solve(nums))

入力

[1, 2, -1, 4, 5, -1]

出力

3

コードのポイント解説

• グラフの構築： 各動物とその捕食者を双方向の辺でつなぎ、無向グラフとして扱います。これにより、根から獲物の方向へも探索できるようになります。
• 根の検出： 値が −1 の動物は捕食者を持たないため、それぞれ独立した木の起点となります。
• スタックによるDFS： 再帰呼び出しの代わりにスタックで (ノード, 深さ) のペアを管理することで、大きな入力でも Python の再帰深度制限を気にせず処理できます。
• 訪問管理： 訪問済みノードや −1（番兵）はスキップすることで、同じノードの再探索を防ぎ、効率を保っています。

計算量については、各ノードと各辺が高々一度ずつ処理されるため、時間計算量・空間計算量ともに O(n) で抑えられます。