{"id":5176,"date":"2019-05-14T09:32:30","date_gmt":"2019-05-14T16:32:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5176"},"modified":"2019-05-14T09:33:51","modified_gmt":"2019-05-14T16:33:51","slug":"leetcode-1042-flower-planting-with-no-adjacent","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1042-flower-planting-with-no-adjacent\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1042. Flower Planting With No Adjacent"},"content":{"rendered":"\n

You have N<\/code> gardens, labelled 1<\/code> to N<\/code>.  In each garden, you want to plant one of 4 types of flowers.<\/p>\n\n\n\n

paths[i] = [x, y]<\/code> describes the existence of a bidirectional path from garden x<\/code> to garden y<\/code>.<\/p>\n\n\n\n

Also, there is no garden that has more than 3 paths coming into or leaving it.<\/p>\n\n\n\n

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.<\/p>\n\n\n\n

Return any<\/strong> such a choice as an array answer<\/code>, where answer[i]<\/code> is the type of flower planted in the (i+1)<\/code>-th garden.  The flower types are denoted 1, 2, 3, or 4.  It is guaranteed an answer exists.<\/p>\n\n\n\n

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

Input: <\/strong>N = 3, paths = [[1,2],[2,3],[3,1]]\nOutput: <\/strong>[1,2,3]\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>N = 4, paths = [[1,2],[3,4]]\nOutput: <\/strong>[1,2,1,2]\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]\nOutput: <\/strong>[1,2,3,4]\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  • 1 <= N <= 10000<\/code><\/li>
  • 0 <= paths.size <= 20000<\/code><\/li>
  • No garden has 4 or more paths coming into or leaving it.<\/li>
  • It is guaranteed an answer exists.<\/li><\/ul>\n\n\n\n
    Solution: Graph coloring, choose any available color<\/strong><\/h2>\n\n\n\n
    Time complexity: O(|V|+|E|)
    Space complexity: O(|V|+|E|)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector gardenNoAdj(int N, vector>& paths) {\n    vector ans(N, 0);\n    vector> G(N);\n    for (const auto& p : paths) {\n      G[p[0] - 1].push_back(p[1] - 1);\n      G[p[1] - 1].push_back(p[0] - 1);\n    }\n    for (int i = 0; i < N; ++i) {      \n      int mask = 0;\n      for (const auto& j : G[i])\n        mask |= (1 << ans[j]);\n      for (int c = 1; c <= 4 && ans[i] == 0; ++c)\n        if (!(mask & (1 << c))) ans[i] = c;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You have N gardens, labelled 1 to N.  In each garden, you want to plant one of 4 types of flowers. paths[i] = [x, y] describes the existence of a bidirectional…<\/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":[346,222,77],"class_list":["post-5176","post","type-post","status-publish","format-standard","hentry","category-graph","tag-coloring","tag-easy","tag-graph","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5176","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=5176"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5176\/revisions"}],"predecessor-version":[{"id":5179,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5176\/revisions\/5179"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5176"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5176"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5176"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}