aboutsummaryrefslogtreecommitdiff
path: root/is_graph_biparite.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'is_graph_biparite.cpp')
-rw-r--r--is_graph_biparite.cpp52
1 files changed, 52 insertions, 0 deletions
diff --git a/is_graph_biparite.cpp b/is_graph_biparite.cpp
new file mode 100644
index 0000000..3f2f853
--- /dev/null
+++ b/is_graph_biparite.cpp
@@ -0,0 +1,52 @@
+// 785. Is Graph Bipartite?
+#include "leetcode.h"
+
+/*
+ * there is an undirected graph with 'n' nodes, where each node is numbered
+ * between 0 and 'n - 1'. you are given a 2d array 'graph' where 'graph[u]' is
+ * an array of nodes that node 'u' is adjacent to. more formally, for each 'v'
+ * in 'graph[u]', there is an undirected edge between node 'u' and node 'v'. the
+ * graph has the following properties:
+ * - there are no self-edges ('graph[u]' does not contain 'u')
+ * - there are no parallel edges ('graph[u]' does not contain duplicate values)
+ * - if 'v' is in 'graph[u]', then 'u' is in 'graph[v]' (the graph is
+ * undirected)
+ * - the graph may not be connected, meaning there may be two nodes 'u' and 'v'
+ * such that there is no path between them a graph is bipartite if the nodes can
+ * be partitioned into two independent sets 'A' and 'B' such that every edge in
+ * the graph connects a node in set 'A' and a node in set 'B'. return true if
+ * and only if the graph is bipartite.
+ */
+
+class Solution {
+public:
+ bool isBipartite(vvd(int) & graph) {
+ int n = graph.size();
+ vector<int> colour(n);
+ queue<int> q;
+ for (int i = 0; i < n; i++) {
+ if (colour[i])
+ continue;
+ colour[i] = 1;
+ for (q.push(i); !q.empty(); q.pop()) {
+ int curr = q.front();
+ for (int neighbour : graph[curr]) {
+ if (!colour[neighbour]) {
+ colour[neighbour] = -colour[curr];
+ q.push(neighbour);
+ } else if (colour[neighbour] == colour[curr])
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) g1 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
+ vvd(int) g2 = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
+ printf("%d\n", obj.isBipartite(g1)); // expect: 0
+ printf("%d\n", obj.isBipartite(g2)); // expect: 1
+}