#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

输入：

7
5
6
1,0
3,1
4,1
5,3
6,1
6,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());
}
}