aboutsummaryrefslogtreecommitdiff
path: root/is_graph_biparite.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /is_graph_biparite.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'is_graph_biparite.c')
-rw-r--r--is_graph_biparite.c79
1 files changed, 79 insertions, 0 deletions
diff --git a/is_graph_biparite.c b/is_graph_biparite.c
new file mode 100644
index 0000000..139625e
--- /dev/null
+++ b/is_graph_biparite.c
@@ -0,0 +1,79 @@
+// 785. Is Graph Bipartite?
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.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.
+ */
+
+bool dfs(int **graph, int graph_size, int *graph_col_size, int *queue,
+ int begin, int end, int *node, bool *paint) {
+ int _end = end;
+ for (int i = begin; i < end; i++) {
+ int pos = queue[i];
+ int colour = node[pos] ? 2 : 1;
+ for (int j = 0; j < graph_col_size[pos]; j++) {
+ int itr = graph[pos][j];
+ if (node[itr] == node[pos])
+ return false;
+ else if (!paint[itr]) {
+ node[itr] = colour;
+ paint[itr] = true;
+ queue[_end] = itr;
+ _end++;
+ }
+ }
+ if (!dfs(graph, graph_size, graph_col_size, queue, end, _end, node, paint))
+ return false;
+ }
+ return true;
+}
+
+bool isBipartite(int **graph, int graph_size, int *graph_col_size) {
+ int *node = calloc(graph_size, sizeof(int));
+ bool *paint = calloc(graph_size, sizeof(int));
+ int *queue = malloc(graph_size * sizeof(int));
+ int idx = 0;
+ for (int i = 0; i < graph_size; i++) {
+ if (!paint[i]) {
+ node[i] = 1;
+ paint[i] = true;
+ for (int j = 0; j < graph_col_size[i]; j++) {
+ int itr = graph[i][j];
+ if (node[itr] == node[i])
+ return false;
+ else if (!paint[itr]) {
+ node[itr] = 2;
+ paint[itr] = true;
+ queue[idx] = itr;
+ idx++;
+ }
+ }
+ if (!dfs(graph, graph_size, graph_col_size, queue, 0, idx, node, paint))
+ return false;
+ }
+ }
+ return true;
+}
+
+int main() {
+ int g1[][4] = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
+ int g2[][4] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
+ int gcs[] = {};
+ printf("%d\n", isBipartite(g1, 5, gcs)); // expect: 0
+ printf("%d\n", isBipartite(g2, 5, gcs)); // expect: 1
+}