785. Is Graph Bipartite?
Tags:
Medium
Skills:
GraphBFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
Time and space complexity
Solution
1function isBipartite(graph: number[][]): boolean {
2 const n = graph.length;
3 const colors = new Array(n).fill(-1);
4
5 for (let i = 0; i < n; i++) {
6 if (colors[i] === -1) {
7 const queue: number[] = [i]
8 colors[i] = 0;
9
10 while (queue.length > 0) {
11 const node = queue.shift()!;
12 const neighbors = graph[node];
13
14 for (const neighbor of neighbors) {
15 if (colors[neighbor] === -1) {
16 colors[neighbor] = 1 - colors[node];
17 queue.push(neighbor)
18 } else if (colors[neighbor] === colors[node]) {
19 return false
20 }
21 }
22 }
23 }
24 }
25 return true;
26};