网易笔试第三题最少语言数求助
第三题最少语言数,只能过13%,有佬帮忙看看哪里有问题吗
思路是用HashSet统计每个语言会的人
然后根据不同语言是否有同一个人会来构建图的边
最后DFS求联通分量
中间统计没有人会的语言(甲骨文)和一门语言都不会的人(笨蛋)
结果是联通分量-1
自己写完测了一个小时感觉没问题,写的很恼火,第4题都不想看就交卷了
public class Main{ public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt(); int m = in.nextInt(); HashSet<Integer>[] languages = new HashSet[m]; Node[] Nodes = new Node[m]; for (int i = 0; i < m; i++) { languages[i] = new HashSet<>(); Nodes[i] = new Node(i, new ArrayList<Integer>()); } int noLanguage = 0; for (int i = 0; i < n; i++) { int k = in.nextInt(); if (k == 0) { noLanguage++; continue; } for (int j = 0; j < k; j++) { int language = in.nextInt(); languages[language-1].add(i); } } int noOne = 0; for (int i = 0; i < m; i++) { if (languages[i].size() == 0) { noOne++; } } for (int i = 0; i < m; i++) { for (int j = i + 1; j < m; j++) { if (!judge(languages[i], languages[j])) { Nodes[i].edges.add(j); } } } int count = 0; boolean[] isReached = new boolean[m]; for (int i = 0; i < m; i++) { if (!isReached[i]) { dfs(Nodes, i, isReached); count++; } } if (noLanguage == n) { System.out.println(n); }else { System.out.println(count - 1 - noOne + noLanguage); } } } public static void dfs(Node[] nodes, int index, boolean[] isReached) { isReached[index] = true; Node node = nodes[index]; for (int i : node.edges) { if (!isReached[i]) { isReached[i] = true; dfs(nodes, i, isReached); } } } public static boolean judge(HashSet<Integer> set1, HashSet<Integer> set2) { for (int i :set1) { if (set2.contains(i)) { return false; } } return true; } } class Node{ int index; ArrayList<Integer> edges; public Node(int index, ArrayList<Integer> edges) { this.index = index; this.edges = edges; } }