bfs + setcolor

xiaolingtong@bilibili.com · xiaolingtong@bilibili.com · commit 227b9e0c8e4a · 2023-11-08T12:39:59.000+08:00
diff --git a/src/com/blankj/medium/_1462/Solution.kt b/src/com/blankj/medium/_1462/Solution.kt
@@ -0,0 +1,59 @@
+package com.blankj.medium._1462
+
+import com.blankj.ext.print
+import com.blankj.structure.MultiDimensionArray
+
+class Solution {
+    fun checkIfPrerequisite(numCourses: Int, prerequisites: Array<IntArray>, queries: Array<IntArray>): List<Boolean> {
+        val graph = mutableMapOf<Int, MutableList<Int>>()
+        repeat(numCourses) { graph[it] = mutableListOf() }
+        val inDegree = IntArray(numCourses)
+        // isPre[i][j] 记录了 i 是否是 j 的先修课
+        val isPre = Array(numCourses) { BooleanArray(numCourses) }
+        for (prerequisite in prerequisites) {
+            ++inDegree[prerequisite[1]]
+            graph[prerequisite[0]]!!.add(prerequisite[1])
+        }
+        val queue = ArrayDeque<Int>()
+        queue.addAll(inDegree.indices.filter { inDegree[it] == 0 })
+        while (queue.isNotEmpty()) {
+            val cur = queue.removeFirst()
+            for (next in graph[cur]!!) {
+                isPre[cur][next] = true
+                // 遍历更新先修课的先修课到当前课程的状态
+                for (i in 0 until numCourses) {
+                    isPre[i][next] = isPre[i][next] or isPre[i][cur]
+                }
+                --inDegree[next]
+                if (inDegree[next] == 0) {
+                    queue.add(next)
+                }
+            }
+        }
+        val res = mutableListOf<Boolean>()
+        for (query in queries) {
+            res.add(isPre[query[0]][query[1]])
+        }
+        return res
+    }
+}
+
+fun main() {
+    Solution().checkIfPrerequisite(
+        2,
+        MultiDimensionArray.createTestData("[[1,0]]"),
+        MultiDimensionArray.createTestData("[[0,1],[1,0]]"),
+    ).print()
+
+    Solution().checkIfPrerequisite(
+        2,
+        emptyArray(),
+        MultiDimensionArray.createTestData("[[1,0],[0,1]]"),
+    ).print()
+
+    Solution().checkIfPrerequisite(
+        3,
+        MultiDimensionArray.createTestData("[[1,2],[1,0],[2,0]]"),
+        MultiDimensionArray.createTestData("[[1,0],[1,2]]"),
+    ).print()
+}
diff --git a/src/com/blankj/medium/_886/Solution.kt b/src/com/blankj/medium/_886/Solution.kt
@@ -0,0 +1,62 @@
+package com.blankj.medium._886
+
+import com.blankj.ext.print
+import com.blankj.structure.MultiDimensionArray
+
+class Solution {
+    private fun setColor(
+        graph: MutableMap<Int, MutableList<Int>>,
+        colors: IntArray,
+        i: Int,
+        color: Int
+    ): Boolean {
+        val queue = ArrayDeque<Int>()
+        colors[i] = color
+        queue.add(i)
+        while (queue.isNotEmpty()) {
+            val cur = queue.removeFirst()
+            for (next in graph[cur]!!) {
+                if (colors[next] >= 0) {
+                    if (colors[next] == colors[cur]) {
+                        return false
+                    }
+                } else {
+                    queue.add(next)
+                    colors[next] = 1 - colors[cur]
+                }
+            }
+        }
+        return true
+    }
+
+    fun possibleBipartition(n: Int, dislikes: Array<IntArray>): Boolean {
+        val colors = IntArray(n + 1) { -1 }
+        val graph = mutableMapOf<Int, MutableList<Int>>()
+        repeat(n + 1) { graph[it] = mutableListOf() }
+        for (edge in dislikes) {
+            graph[edge[0]]?.add(edge[1])
+            graph[edge[1]]?.add(edge[0])
+        }
+        for (i in 1..n) {
+            if (colors[i] == -1 && !setColor(graph, colors, i, 0)) {
+                return false
+            }
+        }
+        return true
+    }
+}
+
+fun main() {
+    Solution().possibleBipartition(
+        4,
+        MultiDimensionArray.createTestData("[[1,2],[1,3],[2,4]]")
+    ).print()
+    Solution().possibleBipartition(
+        3,
+        MultiDimensionArray.createTestData("[[1,2],[1,3],[2,3]]")
+    ).print()
+    Solution().possibleBipartition(
+        5,
+        MultiDimensionArray.createTestData("[[1,2],[2,3],[3,4],[4,5],[1,5]]")
+    ).print()
+}
