#yyds干货盘点# 解决名企真题：小A最多会新认识的多少人

#yyds干货盘点# 解决名企真题：小A最多会新认识的多少人

1.简述：

描述

小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i

输入描述：

第一行聚会的人数：n（n>=3 & n<10000）；第二行小A的编号: ai（ai >= 0 & ai < n)；第三互相认识的数目: m（m>=1 & m< n(n-1)/2）；第4到m+3行为互相认识的对，以','分割的编号。

输出描述：

输出小A最多会新认识的多少人？

示例1

输入：

7561,03,14,15,36,16,5

输出：

3

2.代码实现：

import java.util.*;public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int ai = in.nextInt(); int m = in.nextInt(); int[] memo = new int[n]; memo[ai] = 1; Map> records = new HashMap<>(); for(int i = 0; i < m; i++) { String[] strs = in.next().split(","); int val1 = Integer.parseInt(strs[0]), val2 = Integer.parseInt(strs[1]); if(!records.containsKey(val1)) records.put(val1, new ArrayList()); if(!records.containsKey(val2)) records.put(val2, new ArrayList()); records.get(val1).add(val2); records.get(val2).add(val1); } int count = 0; Deque queue = new ArrayDeque<>(); queue.push(ai); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++) { for(Integer num : records.get(queue.pop())) { if(memo[num] == 0){ memo[num] = 1; queue.push(num); count++; } } } } System.out.println(count - records.get(ai).size()); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。