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.
1from collections import deque
2
3def possible_bipartition(n, dislikes):
4 graph = [[] for _ in range(n + 1)]
5 for u, v in dislikes:
6 graph[u].append(v)
7 graph[v].append(u)
8
9 color = [0] * (n + 1)
10
11 def bfs(node):
12 queue = deque([node])
13 color[node] = 1
14 while queue:
15 current = queue.popleft()
16 for neighbor in graph[current]:
17 if color[neighbor] == 0:
18 color[neighbor] = -color[current]
19 queue.append(neighbor)
20 elif color[neighbor] == color[current]:
21 return False
22 return True
23
24 for i in range(1, n + 1):
25 if color[i] == 0:
26 if not bfs(i):
27 return False
28 return TrueThe Python solution adopts a BFS strategy with a deque (double-ended queue) for traversing and coloring the graph nodes. It checks for conflicting colors between adjacent nodes.
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.