graphs (adjacency lists)P0380

Following the crossroad notes

There are n towns numbered 1 to n. There are m roads between towns, and one road "a b" joins town a and town b.
Roads can be used in both directions. Several roads may join the same two towns, and they count as different roads. For each town, the roads that touch it are put in order.
A road that comes earlier in the input comes first, so among the roads touching a town, the one that appears first in the input is that town's 1st road. There are q route notes. One note has a starting town s and k instructions c₁, c₂, …, c_k. A traveller starts in town s and follows the instructions one at a time from the front. Following an instruction c means taking the c-th road of the current town to the town at the other end of that road. If fewer than c roads touch the current town, that instruction cannot be followed.
The traveller stops in that town and throws away all the remaining instructions. For each note, print on one line the number of the town where the traveller ends up and the number of instructions followed, separated by one space.

Input: The first line has n and m separated by one space.
Each of the next m lines has one road as "a b".
The line after that has q, and each of the next q lines has one note as "s k c₁ c₂ … c_k", separated by single spaces.
2 ≤ n ≤ 50, 1 ≤ m ≤ 200, 1 ≤ a, b ≤ n, a ≠ b, 1 ≤ q ≤ 50, 1 ≤ s ≤ n, 1 ≤ k ≤ 50, 1 ≤ c ≤ 200
Output: q lines.
For each note, the number of the final town and the number of instructions followed

Example 1 · stdin

4 4
1 2
2 3
1 3
3 4
3
1 3 2 3 1
2 4 2 1 3 1
4 2 1 3

stdout

3 3
2 2
4 2

main.py Programming language Runtime version

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

If you turn the road list into 'for each town, the list of towns at the other end of its roads' (an adjacency list), one instruction is followed with a single roads[town][c - 1].
In the example town 1 has 2, 3 and town 3 has 2, 1, 4.
Where the languages differ is how to make 'n + 1 empty lists'.
Trap one: Python [[]] * (n + 1) and JS/TS new Array(n + 1).fill([]) do not make n + 1 empty lists; they point n + 1 times at one and the same list.
The roads of every town get mixed into one list, and the example becomes 2 3, 2 4, 3 2.
In Python write [[] for _ in range(n + 1)], and in JS/TS Array.from({ length: n + 1 }, () => []).
C++ vector<vector<int>> roads(n + 1) and Craykon NewList(n + 1, []) make a separate list for each slot (but filling with a dictionary, as in NewList(n, Dict()), makes every slot point at one and the same dictionary), and in Java and C# a loop puts new ArrayList<>() or new List<int>() into each slot.
C has no growing list, so it uses an array roads[51][200] and an array counting the roads of each town.
Trap two: if you write the road "a b" only at town a, town b cannot see that road.
The example becomes 3 1, 2 0, 4 0.
Trap three: the c-th road is at position c - 1 in a list counted from 0.
Reading roads[town][c] takes the road one place later, and when the last road is chosen, as in the first note of the example, it reads outside the list.
Python stops with an IndexError.
Trap four: if you do not stop at an instruction with too few roads and only skip that instruction, the second note of the example is followed to its last instruction and becomes 1 3.
If you never ask whether there are enough roads, JS and TS give undefined without any error when you read outside an array, so the town number becomes undefined and the program stops with a TypeError only at the next instruction.
For note lines, where you do not know how many numbers a line holds, it is handy to split the whole input on spaces and read in order as Python and JS do, but then you must still move the reading position by k after stopping, or the next note is shifted.
C and C++ also read the remaining instructions to the end and throw them away.

Pythonmain.py · 31 lines

import sys data = 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 lines

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 lines

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 lines

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 lines

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 lines

#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 lines

#include <stdio.h> #define MAXN 50#define MAXM 200 int 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 lines

첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// 새목록(개수, [])은 칸마다 따로 빈 목록을 만들어 준다roads = NewList(n + 1, []);for (i = 0; i < m; i++){    길 = Console.ReadNumbers();    roads[길[0]].Add(길[1]); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다    roads[길[1]].Add(길[0]);} q = Console.ReadNumbers()[0];out = [];for (i = 0; i < q; i++){    쪽지 = Console.ReadNumbers();    town = 쪽지[0];    k = 쪽지[1];    followed = 0;    for (j = 0; j < k; j++)    {        c = 쪽지[2 + j];        if (c > roads[town].Count)        {            break;        }        town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번        followed += 1;    }    out.Add(town + " " + followed);}Console.WriteLine(out.Join("\n"));