刷题笔记26——图论二分图判定

世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言

• visited数组是在如果有环的情况下，防止在图中一直绕圈设置的，类似于剪枝操作，走过了就没必要再走一遍

• path是在探索过程中，记录此次的遍历路径，从而判断是否有环的

• 如果是判断的话，visited是无法判断的，path是可以判断的

• 二分图的题背会板子即可

785. 判断二分图:如果没访问就染色，访问过就判断染色是否匹配

class Solution {
    boolean[] visited;
    int[] color;
    boolean isB = true;
    public boolean isBipartite(int[][] graph) {
        int sz = graph.length;
        color = new int[sz];
        visited =new boolean[sz];
        for(int i=0;i<sz;i++){
            traverse(graph,i,1);
        }
        return isB;
    }

    void traverse(int[][] graph, int n, int col){
        if(visited[n]) return;
        visited[n] = true;
        color[n] = col;
        for(int node:graph[n]){
            if(visited[node]){
                if(color[node]!=(1-col)){
                    isB = false;
                }
            }else{
                traverse(graph,node,1-col);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

886. 可能的二分法:有边的话就需要将两个节点分开，用二分图的思路

class Solution {
    // 遍历构图二分图
    boolean[] visited;
    int[] color;
    boolean isBi = true;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        // 构造的是无向图
        visited = new boolean[n];
        color = new int[n];
        List<Integer>[] graph = generateGraph(n,dislikes);
        for(int i=0;i<n;i++){
            traverse(graph,i,1);
        }
        return isBi;
    }

    void traverse(List<Integer>[] graph,int n,int number){
         if(visited[n]) return;
         visited[n] = true;
         color[n] = number;
         for(int node:graph[n]){
             if(visited[node]){
                 if(color[node]!=1-number){
                     isBi = false;
                 }
             }
             else{
                 traverse(graph,node,1-number);
             }
         }
    }

    List<Integer>[] generateGraph(int n, int[][] dislikes){
        List<Integer>[] graph = new LinkedList[n];
        for(int i=0;i<n;i++){
            graph[i] = new LinkedList();
        }
        for(int i=0;i<dislikes.length;i++){
            graph[dislikes[i][0]-1].add(dislikes[i][1]-1);
            graph[dislikes[i][1]-1].add(dislikes[i][0]-1);
        }
        return graph;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44