{"id":3499,"date":"2018-08-12T01:40:59","date_gmt":"2018-08-12T08:40:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3499"},"modified":"2018-09-04T08:34:21","modified_gmt":"2018-09-04T15:34:21","slug":"leetcode-886-possible-bipartition","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-886-possible-bipartition\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 886. Possible Bipartition"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 886. Possible Bipartition - \u5237\u9898\u627e\u5de5\u4f5c EP217\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/VlZiMD7Iby4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Given a set of\u00a0<code>N<\/code>\u00a0people (numbered\u00a0<code>1, 2, ..., N<\/code>), we would like to split everyone into two groups of\u00a0<strong>any<\/strong>\u00a0size.<\/p>\n<p>Each person may dislike some other people, and they should not go into the same group.<\/p>\n<p>Formally, if\u00a0<code>dislikes[i] = [a, b]<\/code>, it means it is not allowed to put the people numbered\u00a0<code>a<\/code>\u00a0and\u00a0<code>b<\/code>\u00a0into the same group.<\/p>\n<p>Return\u00a0<code>true<\/code>\u00a0if and only if it is possible to split everyone into two groups in this way.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>N = <span id=\"example-input-1-1\">4<\/span>, dislikes = <span id=\"example-input-1-2\">[[1,2],[1,3],[2,4]]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">true<\/span>\r\n<strong>Explanation<\/strong>: group1 [1,4], group2 [2,3]\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>N = <span id=\"example-input-2-1\">3<\/span>, dislikes = <span id=\"example-input-2-2\">[[1,2],[1,3],[2,3]]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">false<\/span>\r\n<\/pre>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>N = <span id=\"example-input-3-1\">5<\/span>, dislikes = <span id=\"example-input-3-2\">[[1,2],[2,3],[3,4],[4,5],[1,5]]<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-3\">false<\/span>\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= N &lt;= 2000<\/code><\/li>\n<li><code>0 &lt;= dislikes.length &lt;= 10000<\/code><\/li>\n<li><code>1 &lt;= dislikes[i][j] &lt;= N<\/code><\/li>\n<li><code>dislikes[i][0] &lt; dislikes[i][1]<\/code><\/li>\n<li>There does not exist\u00a0<code>i != j<\/code>\u00a0for which\u00a0<code>dislikes[i] == dislikes[j]<\/code>.<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3614\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><br \/>\n<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3613\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/886-ep217-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><br \/>\n<\/ins><\/p>\n<h1><strong>Solution: Graph Coloring<\/strong><\/h1>\n<p>Color a node with one color, and color all it&#8217;s disliked nodes with another color, if can not finish return false.<\/p>\n<p>Time complexity: O(V+E)<\/p>\n<p>Space complexity: O(V+E)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ \/ DFS<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 96 ms\r\nclass Solution {\r\npublic:\r\n    bool possibleBipartition(int N, vector&lt;vector&lt;int&gt;&gt;&amp; dislikes) {\r\n      g_ = vector&lt;vector&lt;int&gt;&gt;(N);\r\n      for (const auto&amp; d : dislikes) {\r\n        g_[d[0] - 1].push_back(d[1] - 1);\r\n        g_[d[1] - 1].push_back(d[0] - 1);\r\n      }\r\n      colors_ = vector&lt;int&gt;(N, 0);  \/\/ 0: unknown, 1: red, -1: blue\r\n      for (int i = 0; i &lt; N; ++i)\r\n        if (colors_[i] == 0 &amp;&amp; !dfs(i, 1)) return false;\r\n      return true;      \r\n    }\r\nprivate:\r\n  vector&lt;vector&lt;int&gt;&gt; g_;\r\n  vector&lt;int&gt; colors_;\r\n  bool dfs(int cur, int color) {\r\n    colors_[cur] = color;\r\n    for (int nxt : g_[cur]) {\r\n      if (colors_[nxt] == color) return false;      \r\n      if (colors_[nxt] == 0 &amp;&amp; !dfs(nxt, -color)) return false;\r\n    }\r\n    return true;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ \/ BFS<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 100 ms\r\nclass Solution {\r\npublic:\r\n  bool possibleBipartition(int N, vector&lt;vector&lt;int&gt;&gt;&amp; dislikes) {\r\n    vector&lt;vector&lt;int&gt;&gt; g(N);\r\n    for (const auto&amp; d : dislikes) {\r\n      g[d[0] - 1].push_back(d[1] - 1);\r\n      g[d[1] - 1].push_back(d[0] - 1);\r\n    }\r\n    queue&lt;int&gt; q;\r\n    vector&lt;int&gt; colors(N, 0);  \/\/ 0: unknown, 1: red, -1: blue\r\n    for (int i = 0; i &lt; N; ++i) {\r\n      if (colors[i] != 0) continue;\r\n      q.push(i);\r\n      colors[i] = 1;\r\n      while (!q.empty()) {\r\n        int cur = q.front(); q.pop();\r\n        for (int nxt : g[cur]) {\r\n          if (colors[nxt] == colors[cur]) return false;\r\n          if (colors[nxt] != 0) continue;\r\n          colors[nxt] = -colors[cur];\r\n          q.push(nxt);\r\n        }\r\n      }\r\n    }    \r\n    return true;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problem<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-785-is-graph-bipartite\/\">\u82b1\u82b1\u9171 LeetCode 785. Is Graph Bipartite?<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a set of\u00a0N\u00a0people (numbered\u00a01, 2, &#8230;, N), we would like to split everyone into two groups of\u00a0any\u00a0size. Each person may dislike some other&#8230;<\/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":[372,346,33,77,177,150],"class_list":["post-3499","post","type-post","status-publish","format-standard","hentry","category-graph","tag-bipartite","tag-coloring","tag-dfs","tag-graph","tag-medium","tag-partition","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3499","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=3499"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3499\/revisions"}],"predecessor-version":[{"id":3866,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3499\/revisions\/3866"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3499"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3499"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3499"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}