某个社团有 n 个人，编号为 1 到 n。 给出 m 行好友关系。 一行 "a b" 表示 a 号和 b 号互为好友。 同一个关系可能出现在多行中，也可能以 "a b" 和 "b a" 这样调换顺序的形式出现。 不管出现几次，两人都只是一对好友。 现在要给 x 号推荐一位新好友。 候选人是既不是 x 号本人、也不是 x 号好友的人。 候选人 y 的分数是既是 x 号的好友、又是 y 号的好友的人数。 在分数至少为 1 的候选人中，推荐分数最高的人。 分数相同时推荐编号最小的人。 给出 q 个询问。 每个询问给出一个 x，同一个人可能被问多次。 对每个询问输出一行：推荐的人的编号和他的分数，用一个空格隔开。 如果没有分数至少为 1 的候选人，这一行只输出 -1。
输入
第一行是 n、m、q，用一个空格隔开。 接下来 m 行每行一对 a 和 b，用一个空格隔开。 最后一行是 q 个询问 x，用一个空格隔开。 2 ≤ n ≤ 10,000，0 ≤ m ≤ 10,000，1 ≤ q ≤ 100，1 ≤ a, b, x ≤ n，a ≠ b。 全部是整数
输出
每个询问一行，共 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 把见过的关系记在 字典() 里，用 包含 查询。 陷阱二：关系是双向的。 只把 b 加入 a 的列表而不把 a 加入 b 的列表，得到的是半张图。 陷阱三：好友的好友里一定有 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); }}