leetcode_785_判斷二分圖

題目：

給定一個無向圖graph，當這個圖為二分圖時傳回true。

如果我們能将一個圖的節點集合分割成兩個獨立的子集A和B，并使圖中的每一條邊的兩個節點一個來自A集合，一個來自B集合，我們就将這個圖稱為二分圖。

graph将會以鄰接表方式給出，graph[i]表示圖中與節點i相連的所有節點。每個節點都是一個在0到graph.length-1之間的整數。這圖中沒有自環和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重複的值。

示例 1:

輸入: [[1,3], [0,2], [1,3], [0,2]]

輸出: true

解釋: 

無向圖如下:

0----1

|    |

|    |

3----2

我們可以将節點分成兩組: {0, 2} 和 {1, 3}。

示例 2:

輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]

輸出: false

解釋: 

無向圖如下:

0----1

| \  |

|  \ |

3----2

我們不能将節點分割成兩個獨立的子集。

注意:

graph 的長度範圍為 [1, 100]。

graph[i] 中的元素的範圍為 [0, graph.length - 1]。

graph[i] 不會包含 i 或者有重複的值。

圖是無向的: 如果j 在 graph[i]裡邊, 那麼 i 也會在 graph[j]裡邊。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/is-graph-bipartite

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路：

二分圖是離散數學中圖論章節的内容。二分圖又稱二部圖，即圖（這裡指無向圖）中的的點，可以劃分為兩個部分。劃分的規則為：連線兩端的點分别屬于兩個部其中的一個。稱這樣的圖為二分圖。

在解決該問題時，使用的是染色法。即給點打标簽。

而打标簽的規則為：如果目前點還沒有被打上标簽，則給其打上與其所有鄰點不同的标簽；如果目前點已經打上标簽則continue。

在實作的時候使用1,2,3三種數字來作為“染劑”染色。

由于操作對象是圖，并且需要周遊，是以自然的想到DFS（深度優先搜尋）和BFS（廣度優先搜尋）。

而由于操作對象 圖 不一定是連通圖，是以可能有多個連通分量，這時一次DFS或者BFS就不夠，需要使用一個外循環來控制DFS/BFS的入口：

for(int i = 0;i < lens;i++){
            if(book[i] == 1) continue;
            book[i] = 1;
            dfs(graph, paint, book, i);
        }
           

最後，通常的，實作DFS與BFS時都需要使用一個标簽book數組來記錄已經周遊過的節點。

再由于本題需要給節點打标簽，是以額外需要paint數組記錄每一個節點的分組情況。

實作：

JAVA版：

package leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/*
USER：LQY
DATE：2020/7/16
TIME：8:34
*/
public class leetcode_785 {

    public static void main(String []args){
        int [][]graph = {
                {},
                {2,4,6},
                {1,4,8,9},
                {7,8},
                {1,2,8,9},
                {6,9},
                {1,5,7,8,9},
                {3,6,9},
                {2,3,4,6,9},
                {2,4,5,6,7,8}
        };
        System.out.println("\n"+new leetcode_785().isBipartite(graph));
    }
    public boolean isBipartite(int[][] graph) {

        int lens = graph.length;

        int []paint = new int[lens];
        int []book = new int[lens];
//        DFS
//        for(int i = 0;i < lens;i++){
//            if(book[i] == 1) continue;
//            book[i] = 1;
//            dfs(graph, paint, book, i);
//        }
        //BFS
//        LinkedList<Integer> queen = new LinkedList<>();
//        for(int k = 0;k < lens;k++){
//            if(book[k] == 1) continue;
//            queen.addLast(k);
//            while(!queen.isEmpty()){
//                int nv = queen.removeFirst();
            book[nv] = 1;
//                //添加鄰邊的同時染色
//                int f1 = 0;
//                int f2 = 0;
            int f3 = 0;
//                for(int i = 0;i < graph[nv].length;i++){
//                    int next = graph[nv][i];
//                    if(paint[next] == 1) f1 = 1;
//                    if(paint[next] == 2) f2 = 2;
                if(paint[i] == 3) f3 = 3;
//                    if(book[next] == 1) continue;
//                    queen.addLast(next);
//                    book[next] = 1;
//
//                }
//                //染色
//                if(f1 == 0){
//                    paint[nv] = 1;
//                }else if(f2 == 0){
//                    paint[nv] = 2;
//                }else{
//                    paint[nv] = 3;
//                }
//                System.out.println("點"+nv+"被染成："+paint[nv]);
//            }
//        }
        for(int i : paint){
            System.out.print(i+" ");
        }
        for(int i = 0;i < lens;i++){
            if(paint[i] == 3){
                return false;
            }
        }
        return true;
    }
    public void dfs(int [][]graph, int []paint, int[]book, int nv) {
        if(paint[nv] != 0) return;
        //先判斷該點處是否染色
        int f1 = 0;
        int f2 = 0;
//            int f3 = 0;
        //統計鄰邊染色情況
        for(int i = 0;i < graph[nv].length;i++){
            int next = graph[nv][i];
            if(paint[next] == 1) f1 = 1;
            if(paint[next] == 2) f2 = 2;
//                if(paint[i] == 3) f3 = 3;
        }
        //染色
        if(f1 == 0){
            paint[nv] = 1;
        }else if(f2 == 0){
            paint[nv] = 2;
        }else{
            paint[nv] = 3;
        }
        System.out.println("點"+nv+"被染成："+paint[nv]);

        //深搜
        for(int i = 0;i < graph[nv].length;i++){
            int next = graph[nv][i];
            if(book[next] == 1) continue;
            book[next] = 1;
            dfs(graph, paint, book, next);
        }
    }
}
           

Python版：

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        lens = len(graph)
        paint = [0 for _ in range(lens)]
        book = [0 for _ in range(lens)]
        for i in range(lens):
            if(book[i] > 0):
                continue
            book[i] = 1
            self.dfs(graph, paint, book, i)

        for i in range(lens):
            if(paint[i] == 3):
                return False
        return True

    def dfs(self, graph: List[List[int]], paint: List[int], book: List[int], nv: int):
        if(paint[nv] > 0):
            return
        f1 = 0
        f2 = 0
        for i in range(0, len(graph[nv])):
            next = graph[nv][i]
            if(paint[next] == 1):
                f1 = 1
            if(paint[next] == 2):
                f2 = 2
        if(f1 == 0):
            paint[nv] = 1
        elif(f2 == 0):
            paint[nv] = 2
        else:
            paint[nv] = 3
        for i in range(0, len(graph[nv])):
            next = graph[nv][i]
            if(book[next] == 1):
                continue
            book[next] = 1
            self.dfs(graph, paint, book, next)