Sponsored
Sponsored
This approach uses a BFS traversal to determine if the graph is bipartite. A graph is bipartite if you can color it using two colors such that no two adjacent nodes have the same color. We'll represent people as nodes and dislikes as edges.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for storing the graph structure.
1
The C solution uses a BFS approach to check if the graph can be bipartite. The graph is represented using an adjacency list, and BFS is performed from each uncolored node. If we find a conflict in colors, we return false.
This approach uses a DFS traversal to determine if the graph is bipartite. Similar to BFS, DFS attempts to color the graph using two colors to check if a valid bipartition is possible.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V + E) for graph representation.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAXN 2001
6
7int* graph[MAXN];
8int graphSize[MAXN] = {0};
9int color[MAXN];
10
11bool dfs(int node, int c) {
12 color[node] = c;
13 for (int i = 0; i < graphSize[node]; i++) {
14 int neighbor = graph[node][i];
15 if (color[neighbor] == 0) {
16 if (!dfs(neighbor, -c)) {
17 return false;
18 }
19 } else if (color[neighbor] == c) {
20 return false;
21 }
22 }
23 return true;
24}
25
26bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
27 for (int i = 1; i <= n; i++) {
28 graph[i] = (int*)malloc(sizeof(int) * (n + 1));
29 }
30
31 for (int i = 0; i < dislikesSize; i++) {
32 int u = dislikes[i][0];
33 int v = dislikes[i][1];
34 graph[u][graphSize[u]++] = v;
35 graph[v][graphSize[v]++] = u;
36 }
37
38 memset(color, 0, sizeof(color));
39
40 for (int i = 1; i <= n; i++) {
41 if (color[i] == 0) {
42 if (!dfs(i, 1)) {
43 return false;
44 }
45 }
46 }
47
48 return true;
49}The C solution uses a recursive DFS approach to attempt coloring with two colors. If two adjacent nodes have the same color during the traversal, the graph is not bipartite.