Re: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/is-graph-bipartite/description/
785. Is Graph Bipartite?
給你一個無向圖，判斷他是否是二分圖。
Example 1:
https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets
such that every edge connects a node in one and a node in the other.
Example 2:
https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.
思路：
1.如果一個圖是二分圖，他可以被分成左右兩邊且同一邊的節點彼此都不連通。
2.所以我們可以對任意點的周圍著上不同顏色，如果碰到已經著色過且顏色相同的節點
時，表示這個圖必定不是二分圖。
3.著色可以用DFS或BFS實現。
Java Code：
-------------------------------------------
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] state = new int[n];
for (int i = 0; i < n; i++) {
if (state[i] == 0 && !isBipartite(graph, state, i, 1)) {
return false;
}
}
return true;
}
private boolean isBipartite(int[][] graph, int[] state, int v, int color)
{
if (state[v] != 0) {
return state[v] == color;
}
state[v] = color;
for (int edge : graph[v]) {
if (!isBipartite(graph, state, edge, -color)) {
return false;
}
}
return true;
}
}
-------------------------------------------
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1684517832.A.836.html
推
05/20 01:59,
2年前
, 1F
05/20 01:59, 1F
討論串 (同標題文章)
完整討論串 (本文為第 321 之 719 篇)：