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.
1import java.util.*;
2
3public class Solution {
4 public boolean possibleBipartition(int n, int[][] dislikes) {
5 List<Integer>[] graph = new List[n + 1];
6 for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
7 for (int[] edge : dislikes) {
8 graph[edge[0]].add(edge[1]);
9 graph[edge[1]].add(edge[0]);
10 }
11
12 int[] color = new int[n + 1];
13 Arrays.fill(color, 0);
14
15 for (int i = 1; i <= n; i++) {
16 if (color[i] == 0) {
17 Queue<Integer> queue = new LinkedList<>();
18 queue.offer(i);
19 color[i] = 1;
20 while (!queue.isEmpty()) {
21 int node = queue.poll();
22 for (int neighbor : graph[node]) {
23 if (color[neighbor] == 0) {
24 color[neighbor] = -color[node];
25 queue.offer(neighbor);
26 } else if (color[neighbor] == color[node]) {
27 return false;
28 }
29 }
30 }
31 }
32 }
33 return true;
34 }
35}The Java solution follows a BFS pattern utilizing a queue to color the graph with two colors. Conflict detection is performed by checking neighboring nodes during traversal.
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 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.