# 1761. Minimum Degree of a Connected Trio in a Graph¶

• Time: $O(n^3)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int minTrioDegree(int n, vector>& edges) { int ans = INT_MAX; vector> graph(n); vector degrees(n); for (const vector& edge : edges) { const int u = edge[0] - 1; const int v = edge[1] - 1; // Store the mapping from min(u, v) to max(u, v) to speed up. graph[min(u, v)].insert(max(u, v)); ++degrees[u]; ++degrees[v]; } for (int u = 0; u < n; ++u) for (const int v : graph[u]) for (const int w : graph[u]) if (graph[v].count(w)) ans = min(ans, degrees[u] + degrees[v] + degrees[w] - 6); return ans == INT_MAX ? -1 : ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int minTrioDegree(int n, int[][] edges) { int ans = Integer.MAX_VALUE; Set[] graph = new Set[n]; int[] degrees = new int[n]; for (int i = 0; i < n; ++i) graph[i] = new HashSet<>(); for (int[] edge : edges) { final int u = edge[0] - 1; final int v = edge[1] - 1; // Store the mapping from min(u, v) to max(u, v) to speed up. graph[Math.min(u, v)].add(Math.max(u, v)); ++degrees[u]; ++degrees[v]; } for (int u = 0; u < n; u++) for (final int v : graph[u]) for (final int w : graph[u]) if (graph[v].contains(w)) ans = Math.min(ans, degrees[u] + degrees[v] + degrees[w] - 6); return ans == Integer.MAX_VALUE ? -1 : ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def minTrioDegree(self, n: int, edges: List[List[int]]) -> int: ans = math.inf graph = [set() for _ in range(n)] degrees = [0] * n for u, v in edges: u -= 1 v -= 1 # Store the mapping from min(u, v) to max(u, v) to speed up. graph[min(u, v)].add(max(u, v)) degrees[u] += 1 degrees[v] += 1 for u in range(n): for v in graph[u]: for w in graph[u]: if w in graph[v]: ans = min(ans, degrees[u] + degrees[v] + degrees[w] - 6) return -1 if ans == math.inf else ans