LeetCode Entry

785. Is Graph Bipartite?

19.05.2023 medium 2023 kotlin

Find if graph is bipartite

785. Is Graph Bipartite? medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/217

Problem TLDR

Find if graph is bipartite

Intuition

image.png 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]) }
}