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#include <vector>
2#include <queue>
3using namespace std;
4
5bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
6 vector<vector<int>> graph(n + 1);
7 vector<int> color(n + 1, 0);
8 for (const auto& edge : dislikes) {
9 graph[edge[0]].push_back(edge[1]);
10 graph[edge[1]].push_back(edge[0]);
11 }
12 for (int i = 1; i <= n; ++i) {
13 if (!color[i]) {
14 queue<int> q;
15 q.push(i);
16 color[i] = 1;
17 while (!q.empty()) {
18 int node = q.front(); q.pop();
19 for (int neighbor : graph[node]) {
20 if (!color[neighbor]) {
21 color[neighbor] = -color[node];
22 q.push(neighbor);
23 } else if (color[neighbor] == color[node]) {
24 return false;
25 }
26 }
27 }
28 }
29 }
30 return true;
31}The C++ solution uses a queue-based BFS to try to color the graph. Nodes are colored alternately during traversal. If a node encounters another node with the same color, it denotes a conflict.
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.
1const
The JavaScript solution makes use of a recursive DFS approach to color the graph, checking for color conflicts between directly connected nodes.