LeetCode in Kotlin

886. Possible Bipartition

Medium

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output: true

Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output: false

Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

Constraints:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 104
• dislikes[i].length == 2
• 1 <= ai < bi <= n
• All the pairs of dislikes are unique.

Solution

class Solution {
    fun possibleBipartition(n: Int, dislikes: Array<IntArray>): Boolean {
        // build graph
        val g = Graph(n)
        for (dislike in dislikes) {
            g.addEdge(dislike[0] - 1, dislike[1] - 1)
        }
        val marked = BooleanArray(n)
        val colors = BooleanArray(n)
        for (v in 0 until n) {
            if (!marked[v] && !checkBipartiteDFS(g, marked, colors, v)) {
                // No need to run on other connected components if one component has failed.
                return false
            }
        }
        return true
    }

    private fun checkBipartiteDFS(g: Graph, marked: BooleanArray, colors: BooleanArray, v: Int): Boolean {
        marked[v] = true
        for (w in g.adj(v)) {
            if (!marked[w]) {
                colors[w] = !colors[v]
                if (!checkBipartiteDFS(g, marked, colors, w)) {
                    // this is to break for other neighbours
                    return false
                }
            } else if (colors[v] == colors[w]) {
                return false
            }
        }
        return true
    }

    private class Graph(v: Int) {
        private val adj: Array<ArrayList<Int>?>

        init {
            adj = arrayOfNulls(v)
            for (i in 0 until v) {
                adj[i] = ArrayList<Int>()
            }
        }

        fun addEdge(v: Int, w: Int) {
            adj[v]!!.add(w)
            adj[w]!!.add(v)
        }

        fun adj(v: Int): List<Int> {
            return adj[v]!!
        }
    }
}

This site is open source. Improve this page.