There are n tasks numbered 1 to n.
m conditions are given; a condition "a b" means task b can be done only after task a is finished.
The same condition may be given more than once.
Tasks are done one at a time, and every task is done once.
Each time, among the tasks that can be done now because all tasks they wait for are finished, do the one with the smallest number.
Print the order in which the tasks are done, on one line separated by spaces.
If the conditions make tasks wait for each other so that not all tasks can be done, print only -1.
Input
The first line has n and m; each of the next m lines has a and b separated by a space. 1 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ a, b ≤ n, a ≠ b
Output
The order of the tasks (n numbers on one line, separated by spaces), or -1
Example 1 · stdin
5 4
3 1
3 2
5 4
2 4
stdout
3 1 2 5 4
Example 2 · stdin
3 3
1 2
2 3
3 1
stdout
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
For each task count 'earlier tasks not yet finished' (waiting, the number of incoming arrows); take tasks whose count is 0 and decrease the counts of the tasks after them. A task that reaches 0 goes into the pool of doable tasks (topological sort, Kahn's algorithm — it spreads like breadth-first search). You must always take the smallest number from the pool (greedy), so you need a min-heap (priority queue), not a plain queue: a plain queue (first in, first out) also respects the conditions, but for "6 1, 5 2, 4 3" it gives 4 5 6 3 2 1 (the answer is 4 3 5 2 6 1). Scanning every task for the smallest each time is n² = 100 million steps, past Craykon's execution-step limit (about 50 million). In a cycle, waiting never reaches 0, so if fewer than n tasks come out, print -1 — without that check you print a partial order. When a condition repeats, add it to the adjacency list each time too so it matches waiting (removing duplicates on only one side means a count never reaches 0). Min-heaps differ by language: Python heapq (heappush/heappop on a list, a min-heap), Java PriorityQueue<Integer> (min by default), C# PriorityQueue<int, int> (since .NET 6; value and priority go in separately: Enqueue(t, t)), and C++ std::priority_queue is a max-heap by default, so it needs std::greater<int>. JavaScript, TypeScript, C and Craykon have no heap, so build one on a list: the parent of i is (i - 1) / 2 (integer division — JavaScript >> 1, Craykon Mathf.Quot(i - 1, 2)), the children 2i + 1 and 2i + 2. In TypeScript pop() is number | undefined, so add ! when it is known not to be empty. Craykon lists hold up to 10,000 items, so it subtracts 1 from each number to start at 0, and printing a list with Console.WriteLine(order) joins it with spaces.
Pythonmain.py · 27 lines
import heapqimport sysdata = 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)
JavaScriptmain.js · 63 lines
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");
TypeScriptmain.ts · 66 lines
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");
JavaMain.java · 43 lines
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"); }}
C#Main.cs · 40 lines
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"); }}
C++main.cpp · 41 lines
#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"; }}
Cmain.c · 73 lines
#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;}
Craykonmain.cray · 100 lines
// 최소 힙(목록 heap): heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.Add(x); i = heap.Count - 1; while (i > 0) { 부모 = Mathf.Quot(i - 1, 2); if (heap[부모] <= heap[i]) { break; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }}힙꺼내기(heap){ top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); i = 0; while (true) { l = 2 * i + 1; r = l + 1; small = i; if (l < heap.Count && heap[l] < heap[small]) { small = l; } if (r < heap.Count && heap[r] < heap[small]) { small = r; } if (small == i) { break; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; } return top;}첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 일 번호에서 1을 빼 0번부터 둔다after = []; // after[a] = a를 끝내야 할 수 있는 일들for (t = 0; t < n; t++){ after.Add([]);}waiting = NewList(n, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (i = 0; i < m; i++){ 쌍 = Console.ReadNumbers(); after[쌍[0] - 1].Add(쌍[1] - 1); waiting[쌍[1] - 1] += 1;}ready = []; // 지금 할 수 있는 일들(최소 힙). 늘 가장 작은 번호를 꺼낸다for (t = 0; t < n; t++){ if (waiting[t] == 0) { 힙넣기(ready, t); }}order = [];while (ready.Count > 0){ t = 힙꺼내기(ready); order.Add(t + 1); foreach (next in after[t]) { waiting[next] -= 1; if (waiting[next] == 0) { 힙넣기(ready, next); } }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다if (order.Count == n){ Console.WriteLine(order);}else{ Console.WriteLine(-1);}