有 n 个村子，编号从 1 到 n。 村子之间有 m 条路，一条路 "a b" 连接 a 号村子和 b 号村子。 路可以双向通行。 同样的两个村子之间可能有好几条路，它们算作不同的路。 对每个村子，给通到它的路排上顺序。 在输入里先出现的路排在前面，所以通到某个村子的路中，在输入里最先出现的那条就是这个村子的第 1 条路。 有 q 张指路纸条。 一张纸条上写着出发的村子 s 和 k 个指示 c₁, c₂, …, c_k。 旅人从 s 号村子出发，从前往后一个一个地照着指示走。 照指示 c 走，就是走当前所在村子的第 c 条路，到这条路另一头的村子去。 如果通到当前村子的路不到 c 条，这个指示就没法照做。 旅人停在这个村子，把剩下的指示全部丢掉。 对每张纸条，在一行里输出旅人最后所在村子的编号和照做了的指示个数，用一个空格隔开。
输入
第一行给出 n 和 m，用一个空格隔开。 接下来 m 行每行给出一条路 "a b"。 再下一行给出 q，接下来 q 行每行给出一张纸条 "s k c₁ c₂ … c_k"，用一个空格隔开。 2 ≤ n ≤ 50，1 ≤ m ≤ 200，1 ≤ a, b ≤ n，a ≠ b，1 ≤ q ≤ 50，1 ≤ s ≤ n，1 ≤ k ≤ 50，1 ≤ c ≤ 200
把路的列表改成“每个村子的、各条路另一头的村子的列表”（邻接表），照一个指示走就只要一次 roads[town][c - 1]。 示例中 1 号村子是 2, 3，3 号村子是 2, 1, 4。 各语言不同的地方是怎样做出“n + 1 个空列表”。 陷阱一：Python [[]] * (n + 1) 和 JS、TS new Array(n + 1).fill([]) 并不是做出 n + 1 个空列表，而是把同一个列表指了 n + 1 次。 所有村子的路都混进一个列表里，示例变成 2 3、2 4、3 2。 Python 要写 [[] for _ in range(n + 1)]，JS、TS 要写 Array.from({ length: n + 1 }, () => [])。 C++ vector<vector<int>> roads(n + 1) 和 Craykon 新列表(n + 1, []) 会给每个位置各做一个列表（但像 新列表(n, 字典()) 这样用字典来填，所有位置就指向同一个字典），Java 和 C# 用循环给每个位置放入 new ArrayList<>()、new List<int>()。 C 没有能变长的列表，所以用 roads[51][200] 数组和一个记每个村子有几条路的数组。 陷阱二：如果只把路 "a b" 记在 a 号村子上，从 b 号村子就看不到这条路。 示例变成 3 1、2 0、4 0。 陷阱三：第 c 条路在从 0 数起的列表里是 c - 1 号。 用 roads[town][c] 来读会走后面一条路，而像示例的第一张纸条那样选到最后一条路时，就读到列表外面去了。 Python 会以 IndexError 停下。 陷阱四：如果遇到路不够的指示不停下，只跳过这一个指示，示例的第二张纸条会一直照做到最后一个指示，变成 1 3。 如果根本不问路够不够，JS、TS 读到数组外面也不报错而是给出 undefined，于是村子编号变成 undefined，到下一个指示才以 TypeError 停下。 纸条那几行不知道一行有几个数，像 Python、JS 那样把整个输入按空格切开再依次读会比较方便，但这时停下之后也要把读取位置移动 k，否则下一张纸条就错位了。 C 和 C++ 也要把剩下的指示读完再丢掉。
Pythonmain.py · 31 行
import sysdata = sys.stdin.read().split()pos = 0n, m = int(data[0]), int(data[1])pos = 2# roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로# [[]] * (n + 1)로 만들면 모든 칸이 같은 목록 하나를 가리키므로 칸마다 새 목록을 만든다roads = [[] for _ in range(n + 1)]for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 roads[a].append(b) # 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].append(a)q = int(data[pos])pos += 1out = []for _ in range(q): town, k = int(data[pos]), int(data[pos + 1]) pos += 2 followed = 0 for j in range(k): c = int(data[pos + j]) if c > len(roads[town]): # 그런 길이 없으면 거기서 멈춘다 break town = roads[town][c - 1] # c번째 길은 0부터 세면 c - 1번 followed += 1 pos += k # 버린 지시까지 건너뛴다 out.append(f"{town} {followed}")print("\n".join(out))
JavaScriptmain.js · 30 行
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);let pos = 0;const n = data[pos++];const m = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) { const a = data[pos++]; const b = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q = data[pos++];const out = [];for (let i = 0; i < q; i++) { let town = data[pos++]; const k = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 32 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);let pos = 0;const n: number = data[pos++];const m: number = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < m; i++) { const a: number = data[pos++]; const b: number = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q: number = data[pos++];const out: string[] = [];for (let i = 0; i < q; i++) { let town: number = data[pos++]; const k: number = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c: number = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
JavaMain.java · 45 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;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()); // roads.get(v) = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // 바깥 목록에 칸마다 new ArrayList<>()를 하나씩 넣어야 한다 List<List<Integer>> roads = new ArrayList<>(); for (int v = 0; v <= n; v++) { roads.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); roads.get(a).add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads.get(b).add(a); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); int town = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int followed = 0; for (int j = 0; j < k; j++) { int c = Integer.parseInt(st.nextToken()); if (c > roads.get(town).size()) break; // 그런 길이 없으면 거기서 멈춘다 town = roads.get(town).get(c - 1); // c번째 길은 0부터 세면 c - 1번 followed++; } out.append(town).append(' ').append(followed).append('\n'); } System.out.print(out); }}
C#Main.cs · 47 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int m = int.Parse(first[1]); // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // new List<int>[n + 1]만 하면 칸이 모두 null이라서 칸마다 new List<int>()를 넣어야 한다 var roads = new List<int>[n + 1]; for (int v = 0; v <= n; v++) { roads[v] = new List<int>(); } for (int i = 0; i < m; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int a = int.Parse(p[0]); int b = int.Parse(p[1]); roads[a].Add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].Add(a); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int town = int.Parse(p[0]); int k = int.Parse(p[1]); int followed = 0; for (int j = 0; j < k; j++) { int c = int.Parse(p[2 + j]); if (c > roads[town].Count) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } sb.Append(town).Append(' ').Append(followed).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 行
#include <iostream>#include <vector>using namespace std;int main() { int n, m, q; cin >> n >> m; // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // vector<vector<int>>는 칸마다 따로 빈 vector를 만들어 준다 vector<vector<int>> roads(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; roads[a].push_back(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push_back(a); } cin >> q; for (int i = 0; i < q; i++) { int town, k, followed = 0; bool stopped = false; cin >> town >> k; for (int j = 0; j < k; j++) { int c; cin >> c; // 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 if (stopped) continue; if (c > (int)roads[town].size()) { // 그런 길이 없으면 거기서 멈춘다 stopped = true; continue; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } cout << town << ' ' << followed << '\n'; } return 0;}
Cmain.c · 39 行
#include <stdio.h>#define MAXN 50#define MAXM 200int main(void) { int n, m, q; /* roads[v][i] = v번 마을의 (i + 1)번째 길 건너편 마을, count[v] = v번 마을에 닿은 길의 수 */ /* C에는 늘어나는 목록이 없어서, 한 마을에 길이 모두 몰려도 되도록 칸을 넉넉히 잡는다 */ static int roads[MAXN + 1][MAXM]; static int count[MAXN + 1]; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); roads[a][count[a]++] = b; /* 길은 양쪽으로 다니므로 두 마을 모두에 적는다 */ roads[b][count[b]++] = a; } scanf("%d", &q); for (int i = 0; i < q; i++) { int town, k, followed = 0, stopped = 0; scanf("%d %d", &town, &k); for (int j = 0; j < k; j++) { int c; scanf("%d", &c); /* 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 */ if (stopped) continue; if (c > count[town]) { /* 그런 길이 없으면 거기서 멈춘다 */ stopped = 1; continue; } town = roads[town][c - 1]; /* c번째 길은 0부터 세면 c - 1번 */ followed++; } printf("%d %d\n", town, followed); } return 0;}
Craykonmain.cray · 34 行
첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// 새목록(개수, [])은 칸마다 따로 빈 목록을 만들어 준다roads = 新列表(n + 1, []);循环 (i = 0; i < m; i++){ 길 = 控制台.读数字(); roads[길[0]].添加(길[1]); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[길[1]].添加(길[0]);}q = 控制台.读数字()[0];out = [];循环 (i = 0; i < q; i++){ 쪽지 = 控制台.读数字(); town = 쪽지[0]; k = 쪽지[1]; followed = 0; 循环 (j = 0; j < k; j++) { c = 쪽지[2 + j]; 如果 (c > roads[town].数量) { 跳出; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed += 1; } out.添加(town + " " + followed);}控制台.输出(out.连接("\n"));