Re: [閒聊] 每日LeetCode已回收
886. Possible Bipartition
給你一個數字n表示人數，一個陣列表示a討厭b，找出是否有方法可以將人分成兩組
而且同一組沒有不仲。
Example：
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
思路：
1.想了很久想不出來，看了一下討論才知道是一個著色問題，先建立一個有向圖把
所有討厭的人都雙向連結。
2.從隨便一個點開始用dfs上色，0表示未著色，1和-1分別表示一種顏色，每次上色
都檢查鄰近的點的顏色是否都不同，若出現相同顏色表示討厭的人被分在一起了返
回false。
3.如果整個圖上色完都沒有衝突返回true。
Java Code：
--------------------------------
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int[] e : dislikes) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
int[] colors = new int[n + 1];
for (int s = 1; s <= n; s++) {
if (colors[s] == 0 && dfs(graph, s, colors, 1)) {
return false;
}
}
return true;
}
private boolean dfs(List<List<Integer>> graph, int s, int[] colors, int
color) {
colors[s] = color;
for (int next : graph.get(s)) {
if (colors[next] == -color) continue;
if (colors[next] == color) return true;
if (dfs(graph, next, colors, -color)) return true;
}
return false;
}
}
--------------------------------
對不起我離散數學就是爛
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.8.239 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671604351.A.FB1.html
推
12/21 16:03,
3年前
, 1F
12/21 16:03, 1F
討論串 (同標題文章)
完整討論串 (本文為第 145 之 719 篇)：