亚麻OA最近一道高频新题 "购物模式"

具体题目在这位大佬的帖子里：https://www.1point3acres.com/bbs ... read&tid=672261
找了一下leetcode，发现里面的discuss的链接不work了。自己写了一个，应该是O(VE)的解法。具体思路就是每一个节点走两层BFS，看一下neighbor之间有哎哟有没有相连的。
上面题目帖子里的两个例子都能过。希望大家能一起讨论一下，如果有不对或者可以优化的地方希望大家能指教。谢谢

1. public class Main {
   
2. 
   
3.    
   
4.     public static int getMinScore(int prod_nodes, int prod_edges, int[] froms, int[] tos) {
   
5.         Map<Integer, List<Integer>> graph = new HashMap<>();
   
6.         int n = froms.length;
   
7.         for (int i = 0; i < n; i++) {
   
8.             int from = froms[i];
   
9.             int to = tos[i];
   
10.             graph.putIfAbsent(from, new ArrayList<>());
    
11.             graph.get(from).add(to);
    
12.             graph.putIfAbsent(to, new ArrayList<>());
    
13.             graph.get(to).add(from);
    
14.         }
    
15.         int min = Integer.MAX_VALUE;
    
16.    
    
17.         for(int node : graph.keySet()) {
    
18.             if (graph.get(node).size() < 2) {
    
19.                 continue;
    
20.             }
    
21.             List<Integer> neighbors = graph.get(node);
    
22.             int node_e = neighbors.size();
    
23.             for (int nei : neighbors) {
    
24.                 int nei_e = graph.get(nei).size();
    
25.                 for (int nn : graph.get(nei)) {
    
26.                     if (neighbors.contains(nn)) {
    
27.                         int nn_e = graph.get(nn).size();
    
28.                         int cur = (node_e - 2) + (nei_e - 2) + (nn_e - 2);
    
29.                         min = Math.min(min, cur);
    
30.                     }
    
31.                 }
    
32.             }
    
33.         }
    
34.         return min == Integer.MAX_VALUE? -1 : min;
    
35.     }
    
36.    
    
37. 
    
38.    
    
39.     public static void main(String[] args) {
    
40.         int pn1 = 6;
    
41.         int pe1 = 6;
    
42.         int[] froms1 = new int[] {1,2,2,3,4,5};
    
43.         int[] tos1 = new int[] {2,4,5,5,5,6};
    
44.         System.out.println(getMinScore(pn1, pe1, froms1, tos1));
    
45.         int pn2 = 5;
    
46.         int pe2 = 6;
    
47.         int[] froms2 = new int[] {1,1,2,2,3,4};
    
48.         int[] tos2 = new int[] {2,3,3,4,4,5};
    
49.         System.out.println(getMinScore(pn2, pe2, froms2, tos2));
    
50.     }
    
51. }

复制代码