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, 0 insertions, 52 deletions
diff --git a/is_graph_biparite.cpp b/is_graph_biparite.cpp
deleted file mode 100644
index 4a6b4fc..0000000
--- a/is_graph_biparite.cpp
+++ /dev/null
@@ -1,52 +0,0 @@
-// 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 & 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 g1 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
- vvd 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
-}