{"id":8451,"date":"2021-05-29T15:33:31","date_gmt":"2021-05-29T22:33:31","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8451"},"modified":"2021-05-29T15:36:53","modified_gmt":"2021-05-29T22:36:53","slug":"leetcode-1857-largest-color-value-in-a-directed-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1857-largest-color-value-in-a-directed-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1857. Largest Color Value in a Directed Graph"},"content":{"rendered":"\n

There is a directed graph<\/strong> of n<\/code> colored nodes and m<\/code> edges. The nodes are numbered from 0<\/code> to n - 1<\/code>.<\/p>\n\n\n\n

You are given a string colors<\/code> where colors[i]<\/code> is a lowercase English letter representing the color<\/strong> of the ith<\/sup><\/code> node in this graph (0-indexed<\/strong>). You are also given a 2D array edges<\/code> where edges[j] = [aj<\/sub>, bj<\/sub>]<\/code> indicates that there is a directed edge<\/strong> from node aj<\/sub><\/code> to node bj<\/sub><\/code>.<\/p>\n\n\n\n

A valid path<\/strong> in the graph is a sequence of nodes x1<\/sub> -> x2<\/sub> -> x3<\/sub> -> ... -> xk<\/sub><\/code> such that there is a directed edge from xi<\/sub><\/code> to xi+1<\/sub><\/code> for every 1 <= i < k<\/code>. The color value<\/strong> of the path is the number of nodes that are colored the most frequently<\/strong> occurring color along that path.<\/p>\n\n\n\n

Return the largest color value<\/strong> of any valid path in the given graph, or <\/em>-1<\/code> if the graph contains a cycle<\/em>.<\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> colors = \"abaca\", edges = [[0,1],[0,2],[2,3],[3,4]]\nOutput:<\/strong> 3\nExplanation:<\/strong> The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored \"a\" (red in the above image)<\/code>.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> colors = \"a\", edges = [[0,0]]\nOutput:<\/strong> -1\nExplanation:<\/strong> There is a cycle from 0 to 0.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == colors.length<\/code><\/li>
  • m == edges.length<\/code><\/li>
  • 1 <= n <= 105<\/sup><\/code><\/li>
  • 0 <= m <= 105<\/sup><\/code><\/li>
  • colors<\/code> consists of lowercase English letters.<\/li>
  • 0 <= aj<\/sub>, bj<\/sub> < n<\/code><\/li><\/ul>\n\n\n\n
    Solution: Topological Sorting<\/strong><\/h2>\n\n\n\n
    freq[n][c] := max freq of color c<\/code> after visiting node n<\/code>.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n*26)<\/p>\n\n\n\n
    \n
    python<\/h2>\n
    \n\n
    \nclass Solution:\n  def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n    INF = 1e9\n    n = len(colors)\n    g = [[] for _ in range(n)]\n    for u, v in edges:\n      g[u].append(v)    \n    visited = [0] * n\n    freq = [[0] * 26 for _ in range(n)]\n    def dfs(u: int) -> int:\n      idx = ord(colors[u]) - ord('a')\n      if not visited[u]:\n        visited[u] = 1 # visiting\n        for v in g[u]:\n          if (dfs(v) == INF):\n            return INF\n          for c in range(26):\n            freq[u][c] = max(freq[u][c], freq[v][c])\n        freq[u][idx] += 1\n        visited[u] = 2 # done\n      return freq[u][idx] if visited[u] == 2 else INF\n    ans = 0\n    for u in range(n):\n      ans = max(ans, dfs(u))\n      if ans == INF: break\n    return -1 if ans == INF else ans\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n – 1. You are given a string colors where colors[i] is a lowercase English letter representing the color of the ith node…<\/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,137],"class_list":["post-8451","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hard","tag-topological-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8451","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=8451"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8451\/revisions"}],"predecessor-version":[{"id":8455,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8451\/revisions\/8455"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}