There are n files, numbered 1 to n.
File i has a last-modified time t_i and a list of ingredient files that it is made from.
A file whose ingredient list is empty is a source written by hand, and it is never rebuilt.
Following ingredients never leads back to the same file.
To bring the goal file g up to date, we 'look at' g. Looking at a file x means the following.
If x has already been looked at, do nothing.
Otherwise first look at the ingredients of x one by one, in the order they are listed.
After all of them have been looked at, rebuild x if at least one ingredient was rebuilt this time, or at least one ingredient has a modified time greater than t_x.
An ingredient whose time equals t_x is not newer than x.
A file that is never looked at while looking at g is not rebuilt, even if it is stale.
In the example, looking at file 1 first looks at ingredient 3. File 3 looks at its ingredients 4 and 5, and then is rebuilt because file 5 (70) is newer than itself (60).
Next file 2 is looked at; its ingredient 4 (30) is older than file 2 (40), so it is left alone.
File 1 (80) was modified later than every ingredient, but file 3 has just been rebuilt, so file 1 is rebuilt too.
File 6 is older than its ingredient 5, but it is not used to make file 1, so it is left alone.
Find the files that are rebuilt, in the order they are rebuilt.
Input
The first line has n and g separated by a space. The second line has t_1 to t_n separated by single spaces. Of the next n lines, the i-th has the number of ingredients k of file i followed by the k ingredient numbers, separated by single spaces (just 0 if it has none). No number appears twice in one file's list. 1 ≤ n ≤ 5,000, 1 ≤ g ≤ n, 1 ≤ t_i ≤ 1,000,000,000, the ingredient counts of all files add up to at most 10,000. No path that follows ingredients down from g contains more than 1,000 files, counting g
Output
On the first line, the number of files rebuilt. On the second line, their numbers in the order they are rebuilt, separated by single spaces. If no file is rebuilt, print only 0 on the first line and no second line
Example 1 · stdin
6 1
80 40 60 30 70 10
2 3 2
1 4
2 4 5
0
0
1 5
stdout
2
3 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
Writing a file down only after all its ingredients have been looked at is the 'record on the way out' (post-order) of a depth-first search, and that order is a topological sort: no file comes before its ingredients. Counting incoming edges and taking files out of a queue is also a topological sort, but here only the files the goal needs are built, and in the order the ingredients are listed, so recursion is the fit. Recursion depth differs by language. Python's default limit is 1,000, so a chain of 1,000 ingredients stops with RecursionError; raise it with something like sys.setrecursionlimit(10000). JS, TS, Java, C#, C, C++ and Craykon run at this depth as they are. How a function changes the outer mark lists differs too. In Python an inner function can change a cell of an outer list without nonlocal; Java and C# use static fields, C uses global arrays, and JS, TS and C++ use the outer variables directly. In Craykon a function also changes an outer list directly, as in looked[x] = true;. Trap one: an equal time is not newer. It is >, not >=. Trap two: even if an ingredient's written time is older, once that ingredient has been rebuilt this time the file must be rebuilt as well (file 1 in the example). That is why 'looked at' and 'rebuilt' are separate marks. Trap three: without marking the files already looked at, an ingredient shared by two files is built twice. Trap four: looking at every file from 1 to n also builds stale files the goal does not need (file 6 in the example). Trap five: looking at ingredients sorted by number, or printing the chosen files in number order, changes the order (the example's answer is 3 1, not 1 3).
Pythonmain.py · 37 lines
import syssys.setrecursionlimit(10000) # 재료를 따라 1,000단계까지 내려간다(기본 한도는 1,000)def main(): data = sys.stdin.read().split() n, goal = int(data[0]), int(data[1]) t = [0] + [int(x) for x in data[2:2 + n]] deps = [[]] pos = 2 + n for _ in range(n): k = int(data[pos]) deps.append([int(x) for x in data[pos + 1:pos + 1 + k]]) pos += 1 + k looked = [False] * (n + 1) # 이미 살핀 파일 rebuilt = [False] * (n + 1) # 이번에 다시 만든 파일 order = [] # 다시 만든 차례 def look(x): looked[x] = True stale = False for a in deps[x]: # 재료를 적힌 차례대로 먼저 살핀다 if not looked[a]: look(a) if rebuilt[a] or t[a] > t[x]: stale = True if stale: # 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = True order.append(x) look(goal) print(len(order)) if order: print(" ".join(map(str, order)))main()
JavaScriptmain.js · 34 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n = data[0];const goal = data[1];const t = [0, ...data.slice(2, 2 + n)];const deps = [[]];let pos = 2 + n;for (let i = 0; i < n; i++) { const k = data[pos]; deps.push(data.slice(pos + 1, pos + 1 + k)); pos += 1 + k;}const looked = new Array(n + 1).fill(false); // 이미 살핀 파일const rebuilt = new Array(n + 1).fill(false); // 이번에 다시 만든 파일const order = []; // 다시 만든 차례function look(x) { looked[x] = true; let stale = false; for (const a of deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push(x); }}look(goal);console.log(order.length);if (order.length > 0) console.log(order.join(" "));
TypeScriptmain.ts · 35 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n: number = data[0];const goal: number = data[1];const t: number[] = [0, ...data.slice(2, 2 + n)];const deps: number[][] = [[]];let pos = 2 + n;for (let i = 0; i < n; i++) { const k = data[pos]; deps.push(data.slice(pos + 1, pos + 1 + k)); pos += 1 + k;}const looked: boolean[] = new Array<boolean>(n + 1).fill(false); // 이미 살핀 파일const rebuilt: boolean[] = new Array<boolean>(n + 1).fill(false); // 이번에 다시 만든 파일const order: number[] = []; // 다시 만든 차례function look(x: number): void { looked[x] = true; let stale = false; for (const a of deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push(x); }}look(goal);console.log(order.length);if (order.length > 0) console.log(order.join(" "));
JavaMain.java · 58 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.ArrayList;import java.util.List;public class Main { static int[] t; static int[][] deps; static boolean[] looked; // 이미 살핀 파일 static boolean[] rebuilt; // 이번에 다시 만든 파일 static List<Integer> order = new ArrayList<>(); // 다시 만든 차례 static void look(int x) { looked[x] = true; boolean stale = false; for (int a : deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.add(x); } } public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int goal = (int) in.nval; t = new int[n + 1]; for (int i = 1; i <= n; i++) { in.nextToken(); t[i] = (int) in.nval; } deps = new int[n + 1][]; for (int i = 1; i <= n; i++) { in.nextToken(); int k = (int) in.nval; deps[i] = new int[k]; for (int j = 0; j < k; j++) { in.nextToken(); deps[i][j] = (int) in.nval; } } looked = new boolean[n + 1]; rebuilt = new boolean[n + 1]; look(goal); StringBuilder out = new StringBuilder(); out.append(order.size()).append('\n'); for (int i = 0; i < order.size(); i++) out.append(i > 0 ? " " : "").append(order.get(i)); if (!order.isEmpty()) out.append('\n'); System.out.print(out); }}
C#Main.cs · 50 lines
using System;using System.Collections.Generic;class Program{ static int[] t; static int[][] deps; static bool[] looked; // 이미 살핀 파일 static bool[] rebuilt; // 이번에 다시 만든 파일 static List<int> order = new List<int>(); // 다시 만든 차례 static void Look(int x) { looked[x] = true; bool stale = false; foreach (int a in deps[x]) // 재료를 적힌 차례대로 먼저 살핀다 { if (!looked[a]) Look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) // 재료를 모두 살핀 뒤에야 자기를 만든다 { rebuilt[x] = true; order.Add(x); } } static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), goal = int.Parse(data[1]); t = new int[n + 1]; for (int i = 1; i <= n; i++) t[i] = int.Parse(data[1 + i]); deps = new int[n + 1][]; int pos = 2 + n; for (int i = 1; i <= n; i++) { int k = int.Parse(data[pos]); deps[i] = new int[k]; for (int j = 0; j < k; j++) deps[i][j] = int.Parse(data[pos + 1 + j]); pos += 1 + k; } looked = new bool[n + 1]; rebuilt = new bool[n + 1]; Look(goal); Console.WriteLine(order.Count); if (order.Count > 0) Console.WriteLine(string.Join(" ", order)); }}
C++main.cpp · 44 lines
#include <iostream>#include <vector>std::vector<int> t;std::vector<std::vector<int>> deps;std::vector<bool> looked; // 이미 살핀 파일std::vector<bool> rebuilt; // 이번에 다시 만든 파일std::vector<int> order; // 다시 만든 차례void look(int x) { looked[x] = true; bool stale = false; for (int a : deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push_back(x); }}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, goal; std::cin >> n >> goal; t.assign(n + 1, 0); for (int i = 1; i <= n; i++) std::cin >> t[i]; deps.assign(n + 1, {}); for (int i = 1; i <= n; i++) { int k; std::cin >> k; deps[i].resize(k); for (int &a : deps[i]) std::cin >> a; } looked.assign(n + 1, false); rebuilt.assign(n + 1, false); look(goal); std::cout << order.size() << '\n'; for (std::size_t i = 0; i < order.size(); i++) std::cout << (i ? " " : "") << order[i]; if (!order.empty()) std::cout << '\n';}
Cmain.c · 44 lines
#include <stdio.h>#define MAXN 5001#define MAXM 10000int t[MAXN];int start[MAXN + 1]; /* i번 파일의 재료는 dep[start[i]] … dep[start[i + 1] - 1] */int dep[MAXM + 1];int looked[MAXN]; /* 이미 살핀 파일 */int rebuilt[MAXN]; /* 이번에 다시 만든 파일 */int order[MAXN], made = 0;void look(int x) { looked[x] = 1; int stale = 0; for (int j = start[x]; j < start[x + 1]; j++) { /* 재료를 적힌 차례대로 먼저 살핀다 */ int a = dep[j]; if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = 1; } if (stale) { /* 재료를 모두 살핀 뒤에야 자기를 만든다 */ rebuilt[x] = 1; order[made++] = x; }}int main(void) { int n, goal; scanf("%d %d", &n, &goal); for (int i = 1; i <= n; i++) scanf("%d", &t[i]); int m = 0; for (int i = 1; i <= n; i++) { int k; scanf("%d", &k); start[i] = m; for (int j = 0; j < k; j++) scanf("%d", &dep[m++]); } start[n + 1] = m; look(goal); printf("%d\n", made); for (int i = 0; i < made; i++) printf(i + 1 < made ? "%d " : "%d\n", order[i]); return 0;}
Craykonmain.cray · 48 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];goal = 첫줄[1];t = Console.ReadNumbers(); // t[i - 1]: i번 파일을 고친 시각deps = [];for (i = 0; i < n; i++){ 줄 = Console.ReadNumbers(); 재료 = []; for (j = 1; j <= 줄[0]; j++) { 재료.Add(줄[j] - 1); } deps.Add(재료);}looked = NewList(n, false); // 이미 살핀 파일rebuilt = NewList(n, false); // 이번에 다시 만든 파일order = []; // 다시 만든 차례살피기(x){ looked[x] = true; stale = false; foreach (a in deps[x]) { if (!looked[a]) { 살피기(a); } if (rebuilt[a] || t[a] > t[x]) { stale = true; } } if (stale) { rebuilt[x] = true; order.Add(x + 1); }}살피기(goal - 1);Console.WriteLine(order.Count);if (order.Count > 0){ Console.WriteLine(order.Join(" "));}