n runners numbered 1 to n ran a race, and no two share a rank.
You are given m clues; a clue "a b" means runner a finished before runner b.
The same clue may be given several times, and clues may contradict each other.
Using only the clues, ranks are settled one at a time starting from first place.
Among the runners whose rank is not settled yet, a candidate is a runner for whom every runner written as finishing before them already has a settled rank.
A runner with no clue saying someone finished before them is also a candidate.
If there is exactly one candidate, that runner takes the next rank, and the same step is repeated with the remaining runners.
If there is no candidate or there are two or more, stop there. Also stop when every runner has a rank.
On the first line print the numbers of the runners whose rank was settled, from first place on.
On the second line print the numbers of the candidates at the moment of stopping, in increasing order.
Input
The first line has n and m separated by one space. Each of the next m lines has a and b separated by one space. 1 ≤ n ≤ 50, 0 ≤ m ≤ 200, 1 ≤ a, b ≤ n, a ≠ b
Output
Two lines. Numbers are separated by one space. If no runner's rank was settled, print only - on the first line; if there is no candidate at the moment of stopping, print only - on the second line
Example 1 · stdin
5 5
3 1
1 4
3 1
4 2
4 5
stdout
3 1 4
2 5
Example 2 · stdin
3 3
1 2
2 3
3 2
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
Finding the candidates and taking them out one by one is topological sorting (Kahn's algorithm). For each runner keep waiting, the number of clues saying someone is ahead of them whose rank is not settled yet; a runner with waiting 0 is a candidate. When a candidate's rank is settled, subtract 1 from waiting of every runner written as behind them. An ordinary topological sort picks any candidate when there are several and goes on to the end, but here you move on only when there is exactly one. With only 50 runners, scanning all runners each time without a queue is enough. How to keep a 'runners behind' list per runner differs by language. Python [[] for _ in range(n + 1)], JavaScript/TypeScript Array.from({ length: n + 1 }, () => []), Java adds new ArrayList<>() n+1 times, and C# makes new List<int>[n + 1] and then puts new List<int>() into each slot. C++ vector<vector<int>> after(n + 1) starts with a separate empty vector in every slot. C has no lists, so it stores the clues as they are in two arrays (from, to) and scans them each time. Craykon calls after.Add([]) n+1 times. Trap one: Python [[]] * (n + 1) and JavaScript new Array(n + 1).fill([]) make every slot point to one shared list. In the first example, settling runner 3 then lowers the runner behind in every clue at once, giving 3 and 1 2 4 5. Trap two: in C#, if you forget the new for each slot the slot is null, and the first Add stops with NullReferenceException. Trap three: when a clue appears twice, do not link the runner behind once through a set while counting waiting once per line. Runner 1 in the first example then only drops from 2 to 1, giving 3 and -. Add and count both as many times as the clue appears. Trap four: if you pick the smallest number when there are several candidates and keep going (an ordinary topological sort), the first example gives 3 1 4 2 5 and -. The clues cannot tell which of runners 2 and 5 came first. Trap five: if you do not mark a runner whose rank is settled, their waiting stays 0 and they are counted as a candidate again. The first example gives 3 and 1 3. Trap six: printing an empty list. Python " ".join([]) and JavaScript [].join(" ") are empty strings, so a blank line comes out instead of - (second line of the second example). Joining numbers differs too. Python needs map(str, order) before join, while JavaScript join and C# string.Join take numbers as they are. Java String.join takes only strings, so use a StringBuilder, and C and C++ print in a loop. Craykon joins a list with spaces when you write it, as in Console.WriteLine(order).
Pythonmain.py · 26 lines
import 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) # 아직 등수가 안 정해진 '앞선 선수' 단서의 수for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) after[a].append(b) # 같은 단서가 또 나오면 또 넣고 waiting[b] += 1 # 또 센다(둘이 늘 맞는다)placed = [False] * (n + 1)order = []while True: cand = [v for v in range(1, n + 1) if not placed[v] and waiting[v] == 0] if len(cand) != 1: # 후보가 없거나 여럿이면 멈춘다 break v = cand[0] placed[v] = True order.append(v) for b in after[v]: waiting[b] -= 1# " ".join([])은 빈 문자열이라 빈 목록은 따로 "-"로 쓴다print(" ".join(map(str, order)) if order else "-")print(" ".join(map(str, cand)) if cand else "-")
JavaScriptmain.js · 26 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;// fill([])은 같은 배열 하나를 모든 칸에 넣으니 칸마다 새 배열을 만든다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 placed = new Array(n + 1).fill(false);const order = [];let cand = [];while (true) { cand = []; for (let v = 1; v <= n; v++) if (!placed[v] && waiting[v] === 0) cand.push(v); if (cand.length !== 1) break; // 후보가 없거나 여럿이면 멈춘다 const v = cand[0]; placed[v] = true; order.push(v); for (const b of after[v]) waiting[b]--;}console.log(order.length ? order.join(" ") : "-");console.log(cand.length ? cand.join(" ") : "-");
TypeScriptmain.ts · 26 lines
const data: number[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;// fill([])은 같은 배열 하나를 모든 칸에 넣으니 칸마다 새 배열을 만든다const after: number[][] = Array.from({ length: n + 1 }, () => []); // after[a] = a보다 늦게 들어왔다고 적힌 선수들const waiting: number[] = 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 placed: boolean[] = new Array(n + 1).fill(false);const order: number[] = [];let cand: number[] = [];while (true) { cand = []; for (let v = 1; v <= n; v++) if (!placed[v] && waiting[v] === 0) cand.push(v); if (cand.length !== 1) break; // 후보가 없거나 여럿이면 멈춘다 const v = cand[0]; placed[v] = true; order.push(v); for (const b of after[v]) waiting[b]--;}console.log(order.length ? order.join(" ") : "-");console.log(cand.length ? cand.join(" ") : "-");
JavaMain.java · 43 lines
import java.util.*;public class Main { // 수 목록을 빈칸으로 이어 쓴다(비었으면 "-") static String show(List<Integer> list) { if (list.isEmpty()) return "-"; StringBuilder sb = new StringBuilder(); for (int v : list) { if (sb.length() > 0) sb.append(' '); sb.append(v); } return sb.toString(); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), m = in.nextInt(); List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a보다 늦게 들어왔다고 적힌 선수들 for (int v = 0; v <= n; v++) after.add(new ArrayList<>()); int[] waiting = new int[n + 1]; // 아직 등수가 안 정해진 '앞선 선수' 단서의 수 for (int i = 0; i < m; i++) { int a = in.nextInt(), b = in.nextInt(); after.get(a).add(b); waiting[b]++; } boolean[] placed = new boolean[n + 1]; List<Integer> order = new ArrayList<>(); List<Integer> cand; while (true) { cand = new ArrayList<>(); for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand.add(v); if (cand.size() != 1) break; // 후보가 없거나 여럿이면 멈춘다 int v = cand.get(0); placed[v] = true; order.add(v); for (int b : after.get(v)) waiting[b]--; } System.out.println(show(order)); System.out.println(show(cand)); }}
C#Main.cs · 38 lines
using System;using System.Collections.Generic;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), m = int.Parse(data[1]); var after = new List<int>[n + 1]; // after[a] = a보다 늦게 들어왔다고 적힌 선수들 for (int v = 0; v <= n; v++) after[v] = new List<int>(); // 칸마다 new를 해야 한다(처음에는 null) var waiting = new int[n + 1]; // 아직 등수가 안 정해진 '앞선 선수' 단서의 수 for (int i = 0; i < m; i++) { int a = int.Parse(data[2 + 2 * i]), b = int.Parse(data[3 + 2 * i]); after[a].Add(b); waiting[b]++; } var placed = new bool[n + 1]; var order = new List<int>(); List<int> cand; while (true) { cand = new List<int>(); for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand.Add(v); if (cand.Count != 1) break; // 후보가 없거나 여럿이면 멈춘다 int w = cand[0]; placed[w] = true; order.Add(w); foreach (int b in after[w]) waiting[b]--; } // string.Join은 수 목록도 바로 이어 준다 Console.WriteLine(order.Count > 0 ? string.Join(" ", order) : "-"); Console.WriteLine(cand.Count > 0 ? string.Join(" ", cand) : "-"); }}
C++main.cpp · 43 lines
#include <iostream>#include <vector>using namespace std;// 수 목록을 빈칸으로 이어 쓴다(비었으면 "-")void show(const vector<int>& list) { if (list.empty()) cout << "-"; for (size_t i = 0; i < list.size(); i++) { if (i > 0) cout << ' '; cout << list[i]; } cout << '\n';}int main() { int n, m; cin >> n >> m; vector<vector<int>> after(n + 1); // after[a] = a보다 늦게 들어왔다고 적힌 선수들(칸마다 따로 있는 빈 vector) vector<int> waiting(n + 1, 0); // 아직 등수가 안 정해진 '앞선 선수' 단서의 수 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; after[a].push_back(b); waiting[b]++; } vector<bool> placed(n + 1, false); vector<int> order, cand; while (true) { cand.clear(); for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand.push_back(v); if (cand.size() != 1) break; // 후보가 없거나 여럿이면 멈춘다 int v = cand[0]; placed[v] = true; order.push_back(v); for (int b : after[v]) waiting[b]--; } show(order); show(cand); return 0;}
Cmain.c · 41 lines
#include <stdio.h>#define MAXN 50#define MAXM 200// 수 k개를 빈칸으로 이어 쓴다(없으면 "-")void show(const int *a, int k) { if (k == 0) printf("-"); for (int i = 0; i < k; i++) printf(i ? " %d" : "%d", a[i]); printf("\n");}int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; int from[MAXM], to[MAXM]; // 단서를 그대로 적어 둔다(같은 단서도 그대로) int waiting[MAXN + 1] = {0}; // 아직 등수가 안 정해진 '앞선 선수' 단서의 수 for (int i = 0; i < m; i++) { scanf("%d %d", &from[i], &to[i]); waiting[to[i]]++; } int placed[MAXN + 1] = {0}; int order[MAXN], cand[MAXN]; int count = 0, k = 0; while (1) { k = 0; for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand[k++] = v; if (k != 1) break; // 후보가 없거나 여럿이면 멈춘다 int v = cand[0]; placed[v] = 1; order[count++] = v; for (int i = 0; i < m; i++) if (from[i] == v) waiting[to[i]]--; } show(order, count); show(cand, k); return 0;}
Craykonmain.cray · 57 lines
// 수 목록을 빈칸으로 이어 쓴다(비었으면 "-")보여주기(list){ if (list.Count == 0) { Console.WriteLine("-"); } else { Console.WriteLine(list); // 목록을 쓰면 빈칸으로 이어 쓴다 }}첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];after = []; // after[a] = a보다 늦게 들어왔다고 적힌 선수들for (v = 0; v <= n; v++){ after.Add([]); // 칸마다 새 목록을 만든다}waiting = NewList(n + 1, 0); // 아직 등수가 안 정해진 '앞선 선수' 단서의 수for (i = 0; i < m; i++){ 쌍 = Console.ReadNumbers(); after[쌍[0]].Add(쌍[1]); waiting[쌍[1]] += 1;}placed = NewList(n + 1, false);order = [];cand = [];while (true){ cand = []; for (v = 1; v <= n; v++) { if (!placed[v] && waiting[v] == 0) { cand.Add(v); } } if (cand.Count != 1) { break; // 후보가 없거나 여럿이면 멈춘다 } w = cand[0]; placed[w] = true; order.Add(w); foreach (b in after[w]) { waiting[b] -= 1; }}보여주기(order);보여주기(cand);