{"id":3280,"date":"2018-07-24T09:14:05","date_gmt":"2018-07-24T16:14:05","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3280"},"modified":"2018-08-18T11:03:39","modified_gmt":"2018-08-18T18:03:39","slug":"leetcode-785-is-graph-bipartite","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-785-is-graph-bipartite\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 785. Is Graph Bipartite?"},"content":{"rendered":"<p>Video is for\u00a0<a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-886-possible-bipartition\/\">\u82b1\u82b1\u9171 LeetCode 886. Possible Bipartition<\/a>, but the algorithm is exact the same.<\/p>\n<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>Problem<\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/is-graph-bipartite\/\">https:\/\/leetcode.com\/problems\/is-graph-bipartite\/<\/a><\/p>\n<div class=\"question-description__3U1T\">\n<div>\n<p>Given an undirected\u00a0<code>graph<\/code>, return\u00a0<code>true<\/code>\u00a0if and only if it is bipartite.<\/p>\n<p>Recall that a graph is\u00a0<em>bipartite<\/em>\u00a0if we can split it&#8217;s set of nodes into two independent\u00a0subsets A and B such that every edge in the graph has one node in A and another node in B.<\/p>\n<p>The graph is given in the following form:\u00a0<code>graph[i]<\/code>\u00a0is a list of indexes\u00a0<code>j<\/code>\u00a0for which the edge between nodes\u00a0<code>i<\/code>\u00a0and\u00a0<code>j<\/code>\u00a0exists.\u00a0 Each node is an integer between\u00a0<code>0<\/code>\u00a0and\u00a0<code>graph.length - 1<\/code>.\u00a0 There are no self edges or parallel edges:\u00a0<code>graph[i]<\/code>\u00a0does not contain\u00a0<code>i<\/code>, and it doesn&#8217;t contain any element twice.<\/p>\n<pre class=\"crayon:false\"><strong>Example 1:<\/strong>\r\n<strong>Input:<\/strong> [[1,3], [0,2], [1,3], [0,2]]\r\n<strong>Output:<\/strong> true\r\n<strong>Explanation:<\/strong> \r\nThe graph looks like this:\r\n0----1\r\n|    |\r\n|    |\r\n3----2\r\nWe can divide the vertices into two groups: {0, 2} and {1, 3}.\r\n<\/pre>\n<pre class=\"crayon:false \"><strong>Example 2:<\/strong>\r\n<strong>Input:<\/strong> [[1,2,3], [0,2], [0,1,3], [0,2]]\r\n<strong>Output:<\/strong> false\r\n<strong>Explanation:<\/strong> \r\nThe graph looks like this:\r\n0----1\r\n| \\  |\r\n|  \\ |\r\n3----2\r\nWe cannot find a way to divide the set of nodes into two independent subsets.\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>graph<\/code>\u00a0will have length in range\u00a0<code>[1, 100]<\/code>.<\/li>\n<li><code>graph[i]<\/code>\u00a0will contain integers in range\u00a0<code>[0, graph.length - 1]<\/code>.<\/li>\n<li><code>graph[i]<\/code>\u00a0will not contain\u00a0<code>i<\/code>\u00a0or duplicate values.<\/li>\n<li>The graph is undirected: if any element\u00a0<code>j<\/code>\u00a0is in\u00a0<code>graph[i]<\/code>, then\u00a0<code>i<\/code>\u00a0will be in\u00a0<code>graph[j]<\/code>.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<h1><strong>Solution: Graph Coloring<\/strong><\/h1>\n<p>For each node<\/p>\n<ul>\n<li>If has not been colored, color it to RED(1).<\/li>\n<li>Color its neighbors with a different color RED(1) to BLUE(-1) or BLUE(-1) to RED(-1).<\/li>\n<\/ul>\n<p>If we can finish the coloring then the graph is bipartite. All red nodes on the left no connections between them and all blues nodes on the right, again no connections between them. red and blue nodes are neighbors.<\/p>\n<p>Time complexity: O(V+E)<\/p>\n<p>Space complexity: O(V)<\/p>\n<p>C++ \/ DFS<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  bool isBipartite(vector&lt;vector&lt;int&gt;&gt;&amp; graph) {\r\n    const int n = graph.size();\r\n    vector&lt;int&gt; colors(n);\r\n    for (int i = 0; i &lt; n; ++i)\r\n      if (!colors[i] &amp;&amp; !coloring(graph, colors, 1, i))\r\n        return false;\r\n    return true;\r\n  }\r\nprivate:\r\n  bool coloring(const vector&lt;vector&lt;int&gt;&gt;&amp; graph, vector&lt;int&gt;&amp; colors, int color, int node) {    \r\n    if (colors[node]) return colors[node] == color;\r\n    colors[node] = color;\r\n    for (int nxt : graph[node])\r\n      if (!coloring(graph, colors, -color, nxt)) return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n<h1><strong>Related Problem<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-886-possible-bipartition\/\">\u82b1\u82b1\u9171 LeetCode 886. Possible Bipartition<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Video is for\u00a0\u82b1\u82b1\u9171 LeetCode 886. Possible Bipartition, but the algorithm is exact the same. Problem https:\/\/leetcode.com\/problems\/is-graph-bipartite\/ Given an undirected\u00a0graph, return\u00a0true\u00a0if and only if it is&#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":[346,33,77,177],"class_list":["post-3280","post","type-post","status-publish","format-standard","hentry","category-graph","tag-coloring","tag-dfs","tag-graph","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3280","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=3280"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3280\/revisions"}],"predecessor-version":[{"id":3291,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3280\/revisions\/3291"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}