{"id":8234,"date":"2021-03-13T21:54:57","date_gmt":"2021-03-14T05:54:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8234"},"modified":"2021-03-13T22:11:38","modified_gmt":"2021-03-14T06:11:38","slug":"leetcode-1791-find-center-of-star-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1791-find-center-of-star-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1791. Find Center of Star Graph"},"content":{"rendered":"\n

There is an undirected star<\/strong> graph consisting of n<\/code> nodes labeled from 1<\/code> to n<\/code>. A star graph is a graph where there is one center<\/strong> node and exactly<\/strong> n - 1<\/code> edges that connect the center node with every other node.<\/p>\n\n\n\n

You are given a 2D integer array edges<\/code> where each edges[i] = [ui<\/sub>, vi<\/sub>]<\/code> indicates that there is an edge between the nodes ui<\/sub><\/code> and vi<\/sub><\/code>. Return the center of the given star graph.<\/p>\n\n\n\n

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

Input:<\/strong> edges = [[1,2],[2,3],[4,2]]\nOutput:<\/strong> 2\nExplanation:<\/strong> As shown in the figure above, node 2 is connected to every other node, so 2 is the center.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> edges = [[1,2],[5,1],[1,3],[1,4]]\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 3 <= n <= 105<\/sup><\/code><\/li>
  • edges.length == n - 1<\/code><\/li>
  • edges[i].length == 2<\/code><\/li>
  • 1 <= ui,<\/sub> vi<\/sub> <= n<\/code><\/li>
  • ui<\/sub> != vi<\/sub><\/code><\/li>
  • The given edges<\/code> represent a valid star graph.<\/li><\/ul>\n\n\n\n
    Solution: Graph \/ Hashtable<\/strong><\/h2>\n\n\n\n
    Count the degree of each node, return the one with n-1 degrees.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findCenter(vector>& edges) {\n    unordered_map degrees;\n    for (const auto& e : edges) {\n      ++degrees[e[0]];\n      ++degrees[e[1]];\n    }\n    const int n = degrees.size();\n    for (const auto& [id, d] : degrees)\n      if (d == n - 1) return id;\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Since the center node must appear in each edge, we just need to find the mode of edges[0] + edges[1]<\/p>\n\n\n\n
    Time complexity: O(1)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    Python<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def findCenter(self, e):\n    return mode(e[0] + e[1])\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n – 1 edges that connect the center…<\/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,82,177],"class_list":["post-8234","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8234","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=8234"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8234\/revisions"}],"predecessor-version":[{"id":8237,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8234\/revisions\/8237"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8234"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}