概要

この問題は、タスクの前後関係（依存関係）を保ちつつ、タスクを実行する順番を決定する問題です。条件を満たす順序が複数ある中で「辞書順最小」のものを求める必要があり、依存関係に矛盾（閉路）がある場合はそれを検知して -1 を出力します。

考察

タスクを「頂点」、前提条件（タスク \(A\) の後に \(B\) を行う）を「有向辺 \(A \to B\)」とみなすと、この問題はグラフ理論におけるトポロジカルソートを求める問題に帰着できます。

辞書順最小にするには？

通常のトポロジカルソートでは、次に実行可能なタスク（自分より前に実行すべきタスクがすべて完了したもの）をどれから選んでも構いません。しかし、本問では「辞書順最小」という指定があります。 辞書順を最小にするためには、「今実行可能なタスクの中で、最も番号が小さいタスク」を常に優先して選ぶ必要があります。

矛盾がある場合とは？

「タスク \(1 \to 2\)」「タスク \(2 \to 3\)」「タスク \(3 \to 1\)」のように、依存関係がループ（閉路）を形成している場合、それらのタスクは一生実行することができません。トポロジカルソートの結果、最終的なリストの長さがタスクの総数 \(N\) に満たない場合は、グラフに閉路が含まれている＝矛盾があると判断できます。

アルゴリズム

Kahn（カーン）のアルゴリズムをベースに、データ構造として優先度付きキュー（最小ヒープ）を利用します。

1. 入次数の計算: 各頂点について、自分に向かって伸びている辺の数（入次数）を数えます。
2. 初期化: 入次数が \(0\) の頂点（前提条件がないタスク）をすべて優先度付きキューに入れます。
3. 繰り返し処理: キューが空になるまで以下を繰り返します。
   • キューから最小の番号の頂点 \(u\) を取り出し、結果のリストに追加する。
   • 頂点 \(u\) から出ている辺をすべて削除する。具体的には、\(u\) の隣接頂点 \(v\) の入次数を \(1\) 減らす。
   • 入次数が \(0\) になった頂点 \(v\) があれば、それをキューに追加する。
4. 判定: 結果のリストの長さが \(N\) であればそれを返し、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各頂点と各辺を一度ずつ走査します（\(O(N + M)\)）。
  • 優先度付きキューへの挿入・取り出しに \(O(\log N)\) かかるため、全体で \(O((N + M) \log N)\) となります。
• 空間計算量: \(O(N + M)\)
  • 隣接リストと入次数を管理する配列に \(O(N + M)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() や sys.stdout.write を使うことで実行時間を短縮できます。

• 優先度付きキュー: Python の heapq モジュールは最小ヒープを提供しているため、これを使うだけで常に最小の要素を \(O(\log N)\) で取得でき、辞書順最小の条件を簡単に満たすことができます。

  ソースコード

import sys
import heapq

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します。
    # 大量の入力を処理する場合、sys.stdin.read().split() は Python において効率的です。
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not data:
        return
    
    # イテレータを使用してデータを順番に取得します。
    it = iter(data)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 隣接リストと各ノードの入次数を管理する配列を用意します。
    # タスク番号は 1 から N であるため、サイズを N + 1 にします。
    adj = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    # 前提条件 (Ai, Bi) を読み込み、グラフを構築します。
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            adj[u].append(v)
            in_degree[v] += 1
        except StopIteration:
            break
    
    # 入次数が 0 のノード（前提条件がないタスク）を管理する最小ヒープを用意します。
    # 辞書順最小の順序を求めるため、常に最小の番号のタスクを選択するようにします。
    pq = []
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            heapq.heappush(pq, i)
    
    result = []
    # Kahnのアルゴリズムを用いたトポロジカルソート
    while pq:
        # 入次数 0 のタスクのうち、番号が最小のものを取得します。
        u = heapq.heappop(pq)
        result.append(u)
        
        # 現在のタスクを完了したことで、依存していた後続タスクの入次数を減らします。
        for v in adj[u]:
            in_degree[v] -= 1
            # 入次数が 0 になったタスクは実行可能リスト（ヒープ）に追加します。
            if in_degree[v] == 0:
                heapq.heappush(pq, v)
    
    # すべてのタスクが実行できたか確認します（閉路がある場合は N 個未満になります）。
    if len(result) == N:
        # スペース区切りで出力します。
        sys.stdout.write(" ".join(map(str, result)) + "\n")
    else:
        # すべてのタスクを実行不可能な場合（矛盾がある場合）は -1 を出力します。
        sys.stdout.write("-1\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。