Skip to content

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<vector<int>>& edges) {
    int ans = INT_MAX;
    vector<unordered_set<int>> graph(n);
    vector<int> degrees(n);

    for (const vector<int>& 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<Integer>[] 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