1 番から n 番まで番号のついた仕事が n 個ある。
条件が m 個与えられ、条件一つ "a b" は a 番の仕事を終えてからでないと b 番の仕事ができないことを表す。
同じ条件が何回か与えられることもある。
仕事は一度に一つずつ行い、すべての仕事を一回ずつ行う。
毎回、先にすべき仕事がすべて終わって今できる仕事のうち、番号が最も小さい仕事を行う。
こうしたときの仕事の順番を、空白で区切って一行に出力せよ。
条件のせいで仕事どうしが互いを待ち、すべての仕事をやり終えられないなら、-1 だけを出力する。
5 4 3 1 3 2 5 4 2 4
3 1 2 5 4
3 3 1 2 2 3 3 1
-1
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
仕事ごとに「まだ終わっていない前の仕事の数」（waiting、入ってくる矢印の数）を数え、0 の仕事から取り出して、その後の仕事の数を一つずつ減らします。
0 になった仕事はできる仕事の集まりに入れます（トポロジカルソート、カーンのアルゴリズム — 幅優先探索のように広がります）。
集まりから常に最も小さい番号を取り出す（貪欲）ので、普通のキューではなく最小ヒープ（優先度付きキュー）が要ります：普通のキュー（先に入れたものから）も条件は守りますが、"6 1、5 2、4 3" では 4 5 6 3 2 1 を出します（答えは 4 3 5 2 6 1）。
毎回すべての仕事を見て最小を探すと n² = 1 億回で、Craykon は実行ステップの上限（約 5 千万）を超えます。
輪（循環）があるとその中の仕事は waiting が最後まで 0 にならないので、取り出した仕事が n 個より少なければ -1 です — 確かめないと一部の順番だけを出してしまいます。
同じ条件が何回も来たら、隣接リストにも何回も入れてこそ waiting と合います（片方だけ重複を消すといつまでも 0 になりません）。
最小ヒープは言語ごとに違います：Python heapq（リストに heappush・heappop、最小ヒープ）、Java PriorityQueue<Integer>（既定が最小）、C# PriorityQueue<int, int>（.NET 6 から、値と優先度を別々に入れます：Enqueue(t, t)）、C++ std::priority_queue は既定が最大ヒープなので std::greater<int> を渡す必要があります。
JavaScript・TypeScript・C・Craykon はヒープがないのでリストで自作します：i の親は (i - 1) / 2（整数の割り算 — JavaScript >> 1、Craykon 数学.商(i - 1, 2)）、子は 2i + 1・2i + 2。
TypeScript は pop() が number | undefined なので、空でないときは ! をつけます。
Craykon はリストが 10,000 個までなので番号から 1 を引いて 0 番から入れ、出力はリストを コンソール.書く(order) で書けば空白でつないでくれます。
import heapqimport sys data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) after = [[] for _ in range(n + 1)] # after[a] = a를 끝내야 할 수 있는 일들waiting = [0] * (n + 1) # waiting[b] = b보다 먼저 끝내야 하는데 아직 안 끝난 일의 수for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) after[a].append(b) waiting[b] += 1 # 지금 할 수 있는 일들을 최소 힙에 두고, 늘 가장 작은 번호를 꺼낸다ready = [t for t in range(1, n + 1) if waiting[t] == 0]heapq.heapify(ready)order = []while ready: t = heapq.heappop(ready) order.append(t) for nxt in after[t]: waiting[nxt] -= 1 if waiting[nxt] == 0: heapq.heappush(ready, nxt) # 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다print(" ".join(map(str, order)) if len(order) == n else -1)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap { constructor() { this.items = []; } get size() { return this.items.length; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] <= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l] < a[small]) small = l; if (r < a.length && a[r] < a[small]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }} const after = Array.from({ length: n + 1 }, () => []); // after[a] = a를 끝내야 할 수 있는 일들const waiting = new Array(n + 1).fill(0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; after[a].push(b); waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order = [];while (ready.size > 0) { const t = ready.pop(); order.push(t); for (const next of after[t]) { if (--waiting[next] === 0) ready.push(next); }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap { private items: number[] = []; get size(): number { return this.items.length; } push(x: number): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] <= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): number { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l] < a[small]) small = l; if (r < a.length && a[r] < a[small]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }} const after: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // after[a] = a를 끝내야 할 수 있는 일들const waiting: number[] = new Array<number>(n + 1).fill(0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; after[a].push(b); waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order: number[] = [];while (ready.size > 0) { const t = ready.pop(); order.push(t); for (const next of after[t]) { if (--waiting[next] === 0) ready.push(next); }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a를 끝내야 할 수 있는 일들 for (int t = 0; t <= n; t++) after.add(new ArrayList<>()); int[] waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); after.get(a).add(b); waiting[b]++; } // PriorityQueue는 기본이 최소 힙: poll()이 늘 가장 작은 번호를 꺼낸다 PriorityQueue<Integer> ready = new PriorityQueue<>(); for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.add(t); StringBuilder out = new StringBuilder(); int done = 0; while (!ready.isEmpty()) { int t = ready.poll(); if (done++ > 0) out.append(' '); out.append(t); for (int next : after.get(t)) { if (--waiting[next] == 0) ready.add(next); } } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 System.out.println(done == n ? out.toString() : "-1"); }}using System;using System.Collections.Generic; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int m = int.Parse(first[1]); var after = new List<int>[n + 1]; // after[a] = a를 끝내야 할 수 있는 일들 for (int t = 0; t <= n; t++) after[t] = new List<int>(); var waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { string[] pair = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(pair[0]); int b = int.Parse(pair[1]); after[a].Add(b); waiting[b]++; } // PriorityQueue<값, 우선순위>: 우선순위가 작은 것부터 나온다. 번호를 우선순위로도 쓴다 var ready = new PriorityQueue<int, int>(); for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.Enqueue(t, t); var order = new List<int>(); while (ready.Count > 0) { int t = ready.Dequeue(); order.Add(t); foreach (int next in after[t]) { if (--waiting[next] == 0) ready.Enqueue(next, next); } } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 Console.WriteLine(order.Count == n ? string.Join(" ", order) : "-1"); }}#include <functional>#include <iostream>#include <queue>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::vector<int>> after(n + 1); // after[a] = a를 끝내야 할 수 있는 일들 std::vector<int> waiting(n + 1, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; after[a].push_back(b); waiting[b]++; } // std::priority_queue는 기본이 최대 힙이라 std::greater를 줘서 가장 작은 것이 위로 오게 한다 std::priority_queue<int, std::vector<int>, std::greater<int>> ready; for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.push(t); std::vector<int> order; while (!ready.empty()) { int t = ready.top(); ready.pop(); order.push_back(t); for (int next : after[t]) if (--waiting[next] == 0) ready.push(next); } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 if (static_cast<int>(order.size()) < n) { std::cout << -1 << "\n"; } else { for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << order[i]; std::cout << "\n"; }}#include <stdio.h> #define MAXN 10001#define MAXM 10000 /* 인접 목록을 배열로: head[a]는 a 뒤에 할 수 있는 첫 일 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int waiting[MAXN]; /* 먼저 끝내야 하는데 아직 안 끝난 일의 수 */static int heap[MAXN], heap_size = 0; /* 최소 힙: heap[0]이 가장 작다 */static int order[MAXN]; static void swap(int* x, int* y) { int t = *x; *x = *y; *y = t;} static void heap_push(int x) { int i = heap_size++; heap[i] = x; while (i > 0 && heap[(i - 1) / 2] > heap[i]) { swap(&heap[(i - 1) / 2], &heap[i]); i = (i - 1) / 2; }} static int heap_pop(void) { int top = heap[0]; heap[0] = heap[--heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, small = i; if (l < heap_size && heap[l] < heap[small]) small = l; if (r < heap_size && heap[r] < heap[small]) small = r; if (small == i) break; swap(&heap[small], &heap[i]); i = small; } return top;} int main(void) { int n, m; scanf("%d %d", &n, &m); for (int t = 1; t <= n; t++) head[t] = -1; for (int e = 0; e < m; e++) { int a, b; scanf("%d %d", &a, &b); to[e] = b; next[e] = head[a]; head[a] = e; waiting[b]++; } for (int t = 1; t <= n; t++) if (waiting[t] == 0) heap_push(t); int done = 0; while (heap_size > 0) { int t = heap_pop(); /* 지금 할 수 있는 일 가운데 가장 작은 번호 */ order[done++] = t; for (int e = head[t]; e != -1; e = next[e]) if (--waiting[to[e]] == 0) heap_push(to[e]); } /* 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 */ if (done < n) { puts("-1"); } else { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", order[i]); putchar('\n'); } return 0;}// 최소 힙(목록 heap): heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.追加(x); i = heap.個数 - 1; 間 (i > 0) { 부모 = 数学.商(i - 1, 2); もし (heap[부모] <= heap[i]) { 抜ける; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }} 힙꺼내기(heap){ top = heap[0]; heap[0] = heap[heap.個数 - 1]; heap.位置で取り除く(heap.個数 - 1); i = 0; 間 (真) { l = 2 * i + 1; r = l + 1; small = i; もし (l < heap.個数 && heap[l] < heap[small]) { small = l; } もし (r < heap.個数 && heap[r] < heap[small]) { small = r; } もし (small == i) { 抜ける; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; } 返す top;} 첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 일 번호에서 1을 빼 0번부터 둔다after = []; // after[a] = a를 끝내야 할 수 있는 일들繰り返す (t = 0; t < n; t++){ after.追加([]);}waiting = 新リスト(n, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수繰り返す (i = 0; i < m; i++){ 쌍 = コンソール.数読み(); after[쌍[0] - 1].追加(쌍[1] - 1); waiting[쌍[1] - 1] += 1;} ready = []; // 지금 할 수 있는 일들(최소 힙). 늘 가장 작은 번호를 꺼낸다繰り返す (t = 0; t < n; t++){ もし (waiting[t] == 0) { 힙넣기(ready, t); }}order = [];間 (ready.個数 > 0){ t = 힙꺼내기(ready); order.追加(t + 1); それぞれ (next の中 after[t]) { waiting[next] -= 1; もし (waiting[next] == 0) { 힙넣기(ready, next); } }} // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다もし (order.個数 == n){ コンソール.書く(order);}でなければ{ コンソール.書く(-1);}