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最多会新认识的多少人?
输入:
7
5
6
1,0
3,1
4,1
5,3
6,1
6,5
输出:
3
2.代码实现:
import java.util.*;标签:yyds,真题,int,queue,records,ai,最多会,val2,new From: https://blog.51cto.com/u_15488507/5950839
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());
}
}