{"id":6860,"date":"2020-05-31T10:41:30","date_gmt":"2020-05-31T17:41:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6860"},"modified":"2020-05-31T13:53:53","modified_gmt":"2020-05-31T20:53:53","slug":"leetcode-1466-reorder-routes-to-make-all-paths-lead-to-the-city-zero","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1466-reorder-routes-to-make-all-paths-lead-to-the-city-zero\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1466. Reorder Routes to Make All Paths Lead to the City Zero"},"content":{"rendered":"\n

There are n<\/code> cities numbered from 0<\/code> to n-1<\/code> and n-1<\/code> roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.<\/p>\n\n\n\n

Roads are represented by connections<\/code> where connections[i] = [a, b]<\/code> represents a road from city a<\/code> to b<\/code>.<\/p>\n\n\n\n

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.<\/p>\n\n\n\n

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum<\/strong> number of edges changed.<\/p>\n\n\n\n

It’s guaranteed<\/strong> that each city can reach the city 0 after reorder.<\/p>\n\n\n\n

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

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]\nOutput:<\/strong> 3\nExplanation: <\/strong>Change the direction of edges show in red such that each node can reach the node 0 (capital).<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]\nOutput:<\/strong> 2\nExplanation: <\/strong>Change the direction of edges show in red such that each node can reach the node 0 (capital).<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 3, connections = [[1,0],[2,0]]\nOutput:<\/strong> 0\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 5 * 10^4<\/code><\/li>
  • connections.length == n-1<\/code><\/li>
  • connections[i].length == 2<\/code><\/li>
  • 0 <= connections[i][0], connections[i][1] <= n-1<\/code><\/li>
  • connections[i][0] != connections[i][1]<\/code><\/li><\/ul>\n\n\n\n
    Solution: BFS<\/strong><\/h2>\n\n\n\n
    Augment the graph
    g[u][v] = 1, g[v][u] = 0,  u->v is an edge in the original graph.<\/p>\n\n\n\n
    BFS from 0, sum up all the edge costs to visit all the nodes.<\/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 minReorder(int n, vector>& connections) {\n    vector>> g(n); \/\/ u -> {v, cost}\n    for (const auto& e : connections) {\n      g[e[0]].emplace_back(e[1], 1); \/\/ u -> v, needs flip\n      g[e[1]].emplace_back(e[0], 0); \/\/ v -> u, no cost\n    }\n    int ans = 0;\n    queue q{{0}};\n    vector seen(n);\n    while (!q.empty()) {\n      int cur = q.front(); q.pop();\n      seen[cur] = 1;\n      for (const auto& [nxt, cost] : g[cur]) {\n        if (seen[nxt]) continue;\n        ans += cost;\n        q.push(nxt);\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to…<\/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":[34,77,177],"class_list":["post-6860","post","type-post","status-publish","format-standard","hentry","category-graph","tag-bfs","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6860","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=6860"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6860\/revisions"}],"predecessor-version":[{"id":6865,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6860\/revisions\/6865"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6860"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6860"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}