ある集まりに n 人の人がいて、1 番から n 番まで番号が付いています。 友だち関係が m 行与えられます。 1 行の "a b" は a 番と b 番が互いに友だちであることを表します。 同じ関係が複数の行に出ることがあり、"a b" と "b a" のように順序だけ入れ替わって出ることもあります。 何回出ても二人は一組の友だちにすぎません。 x 番に新しい友だちを一人すすめます。 候補は、x 番自身ではなく、x 番の友だちでもない人です。 候補 y の点数は、x 番とも友だちで y 番とも友だちである人の数です。 点数が 1 以上の候補のうち、点数がいちばん大きい人をすすめます。 点数が同じなら番号がいちばん小さい人をすすめます。 質問が q 個与えられます。 質問ごとに x が一つ与えられ、同じ人について何度も聞かれることがあります。 質問ごとに 1 行に、すすめる人の番号とその点数を空白一つで区切って出力してください。 点数が 1 以上の候補がいなければ、その行に -1 だけを出力します。
入力
1 行目に n, m, q が空白一つで区切られて与えられます。 続く m 行に a と b が 1 行に一組ずつ、空白一つで区切られて与えられます。 最後の行に質問 x が q 個、空白一つで区切られて与えられます。 2 ≤ n ≤ 10,000、0 ≤ m ≤ 10,000、1 ≤ q ≤ 100、1 ≤ a, b, x ≤ n、a ≠ b。 すべて整数です
出力
質問ごとに 1 行ずつ、全部で q 行。 すすめる人の番号と点数、いなければ -1
例 1 · stdin
7 8 4
1 2
1 3
2 4
3 4
2 5
3 5
4 6
2 1
1 6 7 2
stdout
4 2
2 1
-1
3 3
例 2 · stdin
4 5 2
1 2
2 3
3 1
1 2
2 1
1 4
stdout
-1
-1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
グラフを人ごとの友だちリスト（隣接リスト）で持つと、「友だちの友だち」を二重ループでたどれます。 x の友だち f ごとに f の友だち y を見て y の点数を 1 ずつ増やすと、y が f を通って x とつながった回数がそのまま共通の友だちの数になります。 一つ目の例では 1 番の友だちは 2, 3 で、4 番と 5 番がどちらも 2 点なので、番号の小さい 4 番をすすめます。 落とし穴一：同じ関係が何度も出ます（一つ目の例の 1 2 と 2 1）。 そのままリストに入れると同じ友だちが二回入り、点数が二回増えます。 Python の set、JavaScript・TypeScript の Set、Java・C# の HashSet は入れるだけで重複が一つになります。 C++ は vector を sort してから unique と erase で重複を切り落とし、C は関係を a * (n + 1) + b という一つの数にして qsort し、直前と同じものを飛ばします。 Craykon は 辞書() に見た関係を書いておき、含む で確かめます。 落とし穴二：関係は両方向です。 a のリストに b だけ入れて b のリストに a を入れないと、半分のグラフになります。 落とし穴三：友だちの友だちには必ず x 自身が入っています（x → f → x）。 除かないと x に x 自身をすすめてしまいます。 落とし穴四：すでに友だちである人も友だちの友だちになりうるので、候補から除きます（二つ目の例では 2 番と 3 番は互いに友だちですが、1 番にすすめる人はいません）。 落とし穴五：点数が同じなら番号の小さい人です。 Set や辞書をたどる順は番号順ではないので、y < best を自分で比べます。 落とし穴六：点数の配列を質問ごとに使い回す解答（Java、C、C++、Craykon）は、触ったマスを 0 に戻さなければなりません。 配列全体を消すと質問ごとに n マス回ることになるので、触った人だけを集めておいてそのマスだけ消します。 Python・JavaScript・TypeScript・C# は質問ごとに辞書（dict、Map、Dictionary）を新しく作るので消すものがありません。 ないキーの既定値は Python の common.get(y, 0)、JavaScript の common.get(y) ?? 0、C# の GetValueOrDefault(y) で得ます。
Pythonmain.py · 28 行
import sysdata = sys.stdin.read().split()n, m, q = int(data[0]), int(data[1]), int(data[2])# 인접 목록을 집합으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 집합에는 한 번만 들어간다friends = [set() for _ in range(n + 1)]for i in range(m): a, b = int(data[3 + 2 * i]), int(data[4 + 2 * i]) friends[a].add(b) friends[b].add(a)out = []for k in range(q): x = int(data[3 + 2 * m + k]) # 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 common = {} for f in friends[x]: for y in friends[f]: if y != x and y not in friends[x]: # 자기 자신과 이미 친구인 사람은 후보가 아니다 common[y] = common.get(y, 0) + 1 if not common: out.append("-1") continue # 점수가 큰 사람, 같으면 번호가 작은 사람 best = min(common, key=lambda y: (-common[y], y)) out.append(f"{best} {common[best]}")print("\n".join(out))
JavaScriptmain.js · 35 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// 인접 목록을 Set으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 Set에는 한 번만 들어간다const friends = Array.from({ length: n + 1 }, () => new Set());for (let i = 0; i < m; i++) { const a = data[3 + 2 * i]; const b = data[4 + 2 * i]; friends[a].add(b); friends[b].add(a);}const out = [];for (let k = 0; k < q; k++) { const x = data[3 + 2 * m + k]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 const common = new Map(); for (const f of friends[x]) { for (const y of friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (y !== x && !friends[x].has(y)) common.set(y, (common.get(y) ?? 0) + 1); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 let best = -1; let bestCount = 0; for (const [y, c] of common) { if (c > bestCount || (c === bestCount && y < best)) { best = y; bestCount = c; } } out.push(best === -1 ? "-1" : `${best} ${bestCount}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 37 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m, q] = data;// 인접 목록을 Set으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 Set에는 한 번만 들어간다const friends: Set<number>[] = Array.from({ length: n + 1 }, () => new Set<number>());for (let i = 0; i < m; i++) { const a = data[3 + 2 * i]; const b = data[4 + 2 * i]; friends[a].add(b); friends[b].add(a);}const out: string[] = [];for (let k = 0; k < q; k++) { const x = data[3 + 2 * m + k]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 const common = new Map<number, number>(); for (const f of friends[x]) { for (const y of friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (y !== x && !friends[x].has(y)) common.set(y, (common.get(y) ?? 0) + 1); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 let best = -1; let bestCount = 0; for (const [y, c] of common) { if (c > bestCount || (c === bestCount && y < best)) { best = y; bestCount = c; } } out.push(best === -1 ? "-1" : `${best} ${bestCount}`);}console.log(out.join("\n"));
JavaMain.java · 54 行
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; st.nextToken(); int q = (int) st.nval; // 인접 목록을 HashSet으로: friends.get(p) = p의 친구들. 같은 관계가 또 나와도 한 번만 들어간다 List<Set<Integer>> friends = new ArrayList<>(); for (int p = 0; p <= n; p++) friends.add(new HashSet<>()); for (int i = 0; i < m; i++) { st.nextToken(); int a = (int) st.nval; st.nextToken(); int b = (int) st.nval; friends.get(a).add(b); friends.get(b).add(a); } int[] common = new int[n + 1]; // common[y] = 지금 물음에서 y와 함께 아는 친구 수 StringBuilder sb = new StringBuilder(); for (int k = 0; k < q; k++) { st.nextToken(); int x = (int) st.nval; Set<Integer> mine = friends.get(x); // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 List<Integer> touched = new ArrayList<>(); for (int f : mine) { for (int y : friends.get(f)) { if (y == x || mine.contains(y)) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (common[y]++ == 0) touched.add(y); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; for (int y : touched) { if (common[y] > bestCount || (common[y] == bestCount && y < best)) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } if (best == -1) sb.append("-1\n"); else sb.append(best).append(' ').append(bestCount).append('\n'); } System.out.print(sb); }}
C#Main.cs · 51 行
using System;using System.Collections.Generic;using System.Text;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]), q = int.Parse(data[2]); // 인접 목록을 HashSet으로: friends[p] = p의 친구들. 같은 관계가 또 나와도 한 번만 들어간다 var friends = new HashSet<int>[n + 1]; for (int p = 0; p <= n; p++) friends[p] = new HashSet<int>(); for (int i = 0; i < m; i++) { int a = int.Parse(data[3 + 2 * i]), b = int.Parse(data[4 + 2 * i]); friends[a].Add(b); friends[b].Add(a); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { int x = int.Parse(data[3 + 2 * m + k]); // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 var common = new Dictionary<int, int>(); foreach (int f in friends[x]) { foreach (int y in friends[f]) { if (y == x || friends[x].Contains(y)) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 common[y] = common.GetValueOrDefault(y) + 1; } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; foreach (var (y, c) in common) { if (c > bestCount || (c == bestCount && y < best)) { best = y; bestCount = c; } } if (best == -1) sb.Append("-1\n"); else sb.Append(best).Append(' ').Append(bestCount).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 54 行
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; // 인접 목록: friends[p] = p의 친구들 vector<vector<int>> friends(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; friends[a].push_back(b); friends[b].push_back(a); } // 같은 관계가 여러 번 나올 수 있다: 정렬한 다음 unique로 겹친 것을 뒤로 몰고 erase로 잘라 낸다 for (auto &list : friends) { sort(list.begin(), list.end()); list.erase(unique(list.begin(), list.end()), list.end()); } vector<int> common(n + 1, 0); // common[y] = 지금 물음에서 y와 함께 아는 친구 수 vector<int> touched; for (int k = 0; k < q; k++) { int x; cin >> x; const vector<int> &mine = friends[x]; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 touched.clear(); for (int f : mine) { for (int y : friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다(정렬해 두었으니 이분 탐색으로 찾는다) if (y == x || binary_search(mine.begin(), mine.end(), y)) continue; if (common[y]++ == 0) touched.push_back(y); } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, bestCount = 0; for (int y : touched) { if (common[y] > bestCount || (common[y] == bestCount && y < best)) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } if (best == -1) cout << "-1\n"; else cout << best << ' ' << bestCount << '\n'; } return 0;}
Cmain.c · 65 行
#include <stdio.h>#include <stdlib.h>static int cmp_int(const void *p, const void *q) { int a = *(const int *)p, b = *(const int *)q; return (a > b) - (a < b);}int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; // 관계 "a b"를 양쪽 방향의 수 두 개로 적는다: a * (n + 1) + b와 b * (n + 1) + a (1억 남짓이라 int에 든다) int *key = malloc((2 * m + 1) * sizeof(int)); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); key[2 * i] = a * (n + 1) + b; key[2 * i + 1] = b * (n + 1) + a; } // 정렬하면 같은 사람의 친구가 모이고, 같은 관계는 바로 옆에 붙으니 하나만 남긴다 qsort(key, 2 * m, sizeof(int), cmp_int); int *to = malloc((2 * m + 1) * sizeof(int)); // 친구 번호를 사람 차례로 이어 놓은 것 int *start = calloc(n + 2, sizeof(int)); // p의 친구는 to[start[p]] … to[start[p + 1] - 1] int edges = 0; for (int i = 0; i < 2 * m; i++) { if (i > 0 && key[i] == key[i - 1]) continue; to[edges++] = key[i] % (n + 1); start[key[i] / (n + 1) + 1]++; } for (int p = 1; p <= n + 1; p++) start[p] += start[p - 1]; int *common = calloc(n + 1, sizeof(int)); // common[y] = 지금 물음에서 y와 함께 아는 친구 수 int *is_friend = calloc(n + 1, sizeof(int)); // is_friend[y] = 1이면 x의 친구 int *touched = malloc((n + 1) * sizeof(int)); for (int k = 0; k < q; k++) { int x; scanf("%d", &x); for (int e = start[x]; e < start[x + 1]; e++) is_friend[to[e]] = 1; // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 int cnt = 0; for (int e = start[x]; e < start[x + 1]; e++) { int f = to[e]; for (int g = start[f]; g < start[f + 1]; g++) { int y = to[g]; if (y == x || is_friend[y]) continue; // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (common[y]++ == 0) touched[cnt++] = y; } } // 점수가 큰 사람, 같으면 번호가 작은 사람 int best = -1, best_count = 0; for (int i = 0; i < cnt; i++) { int y = touched[i]; if (common[y] > best_count || (common[y] == best_count && y < best)) { best = y; best_count = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } for (int e = start[x]; e < start[x + 1]; e++) is_friend[to[e]] = 0; if (best == -1) printf("-1\n"); else printf("%d %d\n", best, best_count); } free(key); free(to); free(start); free(common); free(is_friend); free(touched); return 0;}
Craykonmain.cray · 79 行
첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];// 인접 목록: friends[p] = p의 친구들(목록은 10,000칸까지라 번호에서 1을 빼 0번부터 둔다)friends = [];繰り返す (p = 0; p < n; p++){ friends.追加([]);}// 같은 관계가 또 나오면 넣지 않는다: 본 관계를 사전에 "작은 번호 * 10000 + 큰 번호"로 적어 둔다본관계 = 辞書();繰り返す (i = 0; i < m; i++){ 쌍 = コンソール.数読み(); a = 数学.小さい方(쌍[0], 쌍[1]) - 1; b = 数学.大きい方(쌍[0], 쌍[1]) - 1; 열쇠 = a * 10000 + b; もし (!본관계.含む(열쇠)) { 본관계[열쇠] = 真; friends[a].追加(b); friends[b].追加(a); }}common = 新リスト(n, 0); // common[y] = 지금 물음에서 y와 함께 아는 친구 수isFriend = 新リスト(n, 偽); // isFriend[y] = x의 친구인가물음들 = コンソール.数読み();それぞれ (물음 の中 물음들){ x = 물음 - 1; それぞれ (f の中 friends[x]) { isFriend[f] = 真; } // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 touched = []; それぞれ (f の中 friends[x]) { それぞれ (y の中 friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 もし (y != x && !isFriend[y]) { もし (common[y] == 0) { touched.追加(y); } common[y] += 1; } } } // 점수가 큰 사람, 같으면 번호가 작은 사람 best = -1; bestCount = 0; それぞれ (y の中 touched) { もし (common[y] > bestCount || common[y] == bestCount && y < best) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } それぞれ (f の中 friends[x]) { isFriend[f] = 偽; } もし (best == -1) { コンソール.書く(-1); } でなければ { コンソール.書く(best + 1 + " " + bestCount); }}