diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /is_graph_biparite.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'is_graph_biparite.c')
-rw-r--r-- | is_graph_biparite.c | 79 |
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 +} |