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.
1const possibleBipartition = (n, dislikes) => {
2 const graph = Array.from({ length: n + 1 }, () => []);
3 for (const [u, v] of dislikes) {
4 graph[u].push(v);
5 graph[v].push(u);
6 }
7
8 const color = new Array(n + 1).fill(0);
9
10 const bfs = (start) => {
11 const queue = [start];
12 color[start] = 1;
13 while (queue.length > 0) {
14 const node = queue.shift();
15 for (const neighbor of graph[node]) {
16 if (color[neighbor] === 0) {
17 color[neighbor] = -color[node];
18 queue.push(neighbor);
19 } else if (color[neighbor] === color[node]) {
20 return false;
21 }
22 }
23 }
24 return true;
25 };
26
27 for (let i = 1; i <= n; i++) {
28 if (color[i] === 0) {
29 if (!bfs(i)) {
30 return false;
31 }
32 }
33 }
34 return true;
35};The JavaScript solution implements BFS for graph coloring. A queue is used for traversal, and nodes are colored in two colors to check for a bipartition.
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
The Python solution employs a recursive DFS approach where each node is colored, and the function checks for conflicts in coloring among connected nodes.