A club has n people numbered 1 to n.
You are given m lines of friendships. A line "a b" means persons a and b are friends with each other.
The same friendship may appear on several lines, and may also appear with the order swapped as "a b" and "b a". However many times it appears, the two people are just one pair of friends.
We want to recommend one new friend to person x.
A candidate is anyone who is not x and is not a friend of x.
The score of candidate y is the number of people who are friends with both x and y.
Among the candidates whose score is at least 1, recommend the one with the highest score. If scores are equal, recommend the one with the smallest number.
There are q questions. Each question gives one x, and the same person may be asked about more than once.
For each question print on one line the number of the recommended person and the score, separated by a single space.
If no candidate has a score of at least 1, print only -1 on that line.
Input
The first line has n, m and q separated by single spaces. The next m lines each have one pair a and b separated by a single space. The last line has the q questions x separated by single spaces. 2 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ q ≤ 100, 1 ≤ a, b, x ≤ n, a ≠ b. All are integers
Output
q lines, one per question: the number of the recommended person and the score, or -1 if there is none
Example 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
Example 2 · stdin
4 5 2
1 2
2 3
3 1
1 2
2 1
1 4
stdout
-1
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
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 store the graph as a list of friends for each person (an adjacency list), you can walk over 'friends of friends' with two nested loops. For each friend f of x, look at each friend y of f and add 1 to y's score; the number of times y is reached from x through some f is exactly the number of friends in common. In the first example person 1's friends are 2 and 3, and persons 4 and 5 both score 2, so the smaller number 4 is recommended. Trap one: the same friendship appears more than once (1 2 and 2 1 in the first example). If you just append, the same friend is in the list twice and the score goes up twice. Python set, JavaScript/TypeScript Set and Java/C# HashSet keep only one copy when you add. C++ sorts the vector and cuts off duplicates with unique and erase; C writes each friendship as the single number a * (n + 1) + b, sorts with qsort and skips a key equal to the one before it. Craykon records the friendships it has seen in a Dict() and asks with Contains. Trap two: a friendship goes both ways. Adding b to a's list without adding a to b's list gives half a graph. Trap three: x is always among the friends of friends (x → f → x). If you do not exclude it, x gets recommended to x. Trap four: someone who is already a friend can also be a friend of a friend and must be excluded (in the second example persons 2 and 3 are friends of each other, yet there is no one to recommend to person 1). Trap five: on equal scores the smaller number wins. Iterating a Set or a dictionary does not go in number order, so compare y < best yourself. Trap six: solutions that reuse one score array for every question (Java, C, C++, Craykon) must set the touched cells back to 0. Clearing the whole array costs n steps per question, so they collect the people they touched and clear only those cells. Python, JavaScript, TypeScript and C# make a new dictionary (dict, Map, Dictionary) for each question, so there is nothing to clear. The default for a missing key comes from common.get(y, 0) in Python, common.get(y) ?? 0 in JavaScript and GetValueOrDefault(y) in C#.
Pythonmain.py · 28 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];// 인접 목록: friends[p] = p의 친구들(목록은 10,000칸까지라 번호에서 1을 빼 0번부터 둔다)friends = [];for (p = 0; p < n; p++){ friends.Add([]);}// 같은 관계가 또 나오면 넣지 않는다: 본 관계를 사전에 "작은 번호 * 10000 + 큰 번호"로 적어 둔다본관계 = Dict();for (i = 0; i < m; i++){ 쌍 = Console.ReadNumbers(); a = Mathf.Min(쌍[0], 쌍[1]) - 1; b = Mathf.Max(쌍[0], 쌍[1]) - 1; 열쇠 = a * 10000 + b; if (!본관계.Contains(열쇠)) { 본관계[열쇠] = true; friends[a].Add(b); friends[b].Add(a); }}common = NewList(n, 0); // common[y] = 지금 물음에서 y와 함께 아는 친구 수isFriend = NewList(n, false); // isFriend[y] = x의 친구인가물음들 = Console.ReadNumbers();foreach (물음 in 물음들){ x = 물음 - 1; foreach (f in friends[x]) { isFriend[f] = true; } // 친구의 친구를 모두 훑으며 후보마다 '함께 아는 친구' 수를 센다 touched = []; foreach (f in friends[x]) { foreach (y in friends[f]) { // 자기 자신과 이미 친구인 사람은 후보가 아니다 if (y != x && !isFriend[y]) { if (common[y] == 0) { touched.Add(y); } common[y] += 1; } } } // 점수가 큰 사람, 같으면 번호가 작은 사람 best = -1; bestCount = 0; foreach (y in touched) { if (common[y] > bestCount || common[y] == bestCount && y < best) { best = y; bestCount = common[y]; } common[y] = 0; // 다음 물음을 위해 센 것을 지운다 } foreach (f in friends[x]) { isFriend[f] = false; } if (best == -1) { Console.WriteLine(-1); } else { Console.WriteLine(best + 1 + " " + bestCount); }}