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

1.简述：

描述

小A参加了一个n人的活动，每个人都有一个唯一编号i(i>=0 & i<n)，其中m对相互认识，在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后，小A最多会认识多少人？

输入描述：

第一行聚会的人数：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<Integer, List<Integer>> 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<Integer>()); if(!records.containsKey(val2)) records.put(val2, new ArrayList<Integer>()); records.get(val1).add(val2); records.get(val2).add(val1); } int count = 0; Deque<Integer> 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()); }}