有 n 个文件，编号从 1 到 n。 第 i 个文件有最后修改时间 t_i，以及制作它时要用的材料文件列表。 材料列表为空的文件是人直接写的原件，不会被重做。 沿着材料走下去不会回到同一个文件。 为了让目标文件 g 变成最新，要“检查”g。 检查文件 x 的意思如下。 如果 x 已经检查过，就什么也不做。 否则先按列表中写的顺序逐个检查 x 的材料。 材料全部检查完之后，如果材料中至少有一个是这次重做过的，或者至少有一个的修改时间大于 t_x，就重做 x。 修改时间与 t_x 相同的材料不算比 x 新。 在检查 g 的过程中一次也没被检查到的文件，即使过期也不重做。 在样例中，检查 1 号时先检查材料 3 号。 3 号检查完材料 4 号和 5 号后，因为 5 号（70）比自己（60）新，所以重做。 接着检查 2 号，它的材料 4 号（30）比 2 号（40）旧，所以保持不变。 1 号（80）比所有材料修改得都晚，但 3 号刚刚重做过，所以 1 号也重做。 6 号比材料 5 号旧，但制作 1 号用不到它，所以保持不变。 请按重做的顺序求出被重做的文件。
输入
第一行给出 n 和 g，用空格分隔。 第二行给出 t_1 到 t_n，用一个空格分隔。 接下来 n 行中的第 i 行给出 i 号文件的材料数 k 和 k 个材料编号，用一个空格分隔（没有材料时只有 0）。 同一个文件的材料列表中不会出现两次相同的编号。 1 ≤ n ≤ 5,000，1 ≤ g ≤ n，1 ≤ t_i ≤ 1,000,000,000，所有文件的材料数之和不超过 10,000。 从 g 沿着材料往下走的任何一条路上，包括 g 在内文件不超过 1,000 个
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = 控制台.读数字();n = 첫줄[0];goal = 첫줄[1];t = 控制台.读数字(); // t[i - 1]: i번 파일을 고친 시각deps = [];循环 (i = 0; i < n; i++){ 줄 = 控制台.读数字(); 재료 = []; 循环 (j = 1; j <= 줄[0]; j++) { 재료.添加(줄[j] - 1); } deps.添加(재료);}looked = 新列表(n, 假); // 이미 살핀 파일rebuilt = 新列表(n, 假); // 이번에 다시 만든 파일order = []; // 다시 만든 차례살피기(x){ looked[x] = 真; stale = 假; 遍历 (a 在 deps[x]) { 如果 (!looked[a]) { 살피기(a); } 如果 (rebuilt[a] || t[a] > t[x]) { stale = 真; } } 如果 (stale) { rebuilt[x] = 真; order.添加(x + 1); }}살피기(goal - 1);控制台.输出(order.数量);如果 (order.数量 > 0){ 控制台.输出(order.连接(" "));}