{"id":8111,"date":"2021-02-13T22:17:03","date_gmt":"2021-02-14T06:17:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8111"},"modified":"2021-02-13T22:18:26","modified_gmt":"2021-02-14T06:18:26","slug":"leetcode-1761-minimum-degree-of-a-connected-trio-in-a-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1761-minimum-degree-of-a-connected-trio-in-a-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph"},"content":{"rendered":"\n

You are given an undirected graph. You are given an integer n<\/code> which is the number of nodes in the graph and an array edges<\/code>, where each edges[i] = [ui<\/sub>, vi<\/sub>]<\/code> indicates that there is an undirected edge between ui<\/sub><\/code> and vi<\/sub><\/code>.<\/p>\n\n\n\n

A connected trio<\/strong> is a set of three<\/strong> nodes where there is an edge between every<\/strong> pair of them.<\/p>\n\n\n\n

The degree of a connected trio<\/strong> is the number of edges where one endpoint is in the trio, and the other is not.<\/p>\n\n\n\n

Return the minimum<\/strong> degree of a connected trio in the graph, or<\/em> -1<\/code> if the graph has no connected trios.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]\nOutput:<\/strong> 3\nExplanation:<\/strong> There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]\nOutput:<\/strong> 0\nExplanation:<\/strong> There are exactly three trios:\n1) [1,4,3] with degree 0.\n2) [2,5,6] with degree 2.\n3) [5,6,7] with degree 2.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 400<\/code><\/li>
  • edges[i].length == 2<\/code><\/li>
  • 1 <= edges.length <= n * (n-1) \/ 2<\/code><\/li>
  • 1 <= ui<\/sub>, vi<\/sub> <= n<\/code><\/li>
  • ui <\/sub>!= vi<\/sub><\/code><\/li>
  • There are no repeated edges.<\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Try all possible Trios.<\/p>\n\n\n\n
    Time complexity: O(n^3)
    Space complexity: O(n^2)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minTrioDegree(int n, vector>& edges) {\n    vector> g(n);\n    for (const auto& e : edges) {\n      g[e[0] - 1].set(e[1] - 1);\n      g[e[1] - 1].set(e[0] - 1);\n    }\n    size_t ans = INT_MAX;\n    for (int i = 0; i < n; ++i)\n      for (int j = i + 1; j < n; ++j)\n        if (g[i][j])\n          for (int k = j + 1; k < n; ++k)\n            if (g[i][k] && g[j][k])\n              ans = min(ans, g[i].count() + g[j].count() + g[k].count() - 6);\n    return ans == INT_MAX ? -1 : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] =…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,217],"class_list":["post-8111","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8111","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8111"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8111\/revisions"}],"predecessor-version":[{"id":8113,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8111\/revisions\/8113"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}