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: