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.
1import
The Java solution utilizes a recursive DFS method to attempt graph coloring. This process ensures that no two connected nodes receive the same color.