# 19.05.2023 [785. Is Graph Bipartite?]

19.05.2023

785. Is Graph Bipartite? medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/217

Problem TLDR

Find if graph is bipartite

Intuition

Mark edge Red or Blue and it’s nodes in the opposite.

Approach

• there are disconnected nodes, so run DFS for all of them

Complexity

• Time complexity:
  O(VE), DFS once for all vertices and edges

• Space complexity:
  O(V+E), for reds and visited set.

Code

    fun isBipartite(graph: Array<IntArray>): Boolean {
        val reds = IntArray(graph.size)
        fun dfs(u: Int, isRed: Int): Boolean {
            if (reds[u] == 0) {
                reds[u] = if (isRed == 0) 1 else isRed
                return graph[u].all { dfs(it, -reds[u]) }
            } else return reds[u] == isRed
        }
        return graph.indices.all { dfs(it, reds[it]) }
    }