写的有点复杂,期待比较精妙的方法
小A最多会新认识的多少人
http://www.nowcoder.com/questionTerminal/1fe6c3136d2a45fa8ef555b459b6dd26
1111ms通过
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()); } }