const dfs = (
graph: number[][],
colors: number[],
node: number,
color: number
): boolean => {
if (colors[node] !== 0) {
return colors[node] === color
}
colors[node] = color
for (const neighbor of graph[node]) {
if (!dfs(graph, colors, neighbor, -color)) {
return false
}
}
return true
}
export const isBipartite = (graph: number[][]): boolean => {
const n: number = graph.length
const colors: number[] = new Array(n).fill(0)
for (let i = 0; i < n; i++) {
if (colors[i] === 0 && !dfs(graph, colors, i, 1)) {
return false
}
}
return true
}