6
#yyds干货盘点# 解决名企真题：小A最多会新认识的多少人
source link: https://blog.51cto.com/u_15488507/5500560
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#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最多会新认识的多少人？
示例17
5
6
1,0
3,1
4,1
5,3
6,1
6,5
5
6
1,0
3,1
4,1
5,3
6,1
6,5
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());
}
}
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());
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK