力扣labuladong一刷day45天二分图判定

2023-12-23 17:52:32

力扣labuladong一刷day45天二分图判定

一、785. 判断二分图

题目链接:https://leetcode.cn/problems/is-graph-bipartite/
思路:二分图指的是每一个节点与它相邻的节点归属不同类别,一共就两种类别。关系就如同一篇文章引用很多题目,一个题目被很多文章引用。解本题只需要遍历,然后在遍历的过程中判断,关键点在于节点间如何标识。递归方法的参数v是父节点,for循环出来的u是子节点,只需要让这两对保持不同即可

class Solution {
   boolean flag = true;
    boolean[] visited;
    boolean[] colors;
    public boolean isBipartite(int[][] graph) {
        visited = new boolean[graph.length];
        colors = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                traverse(graph,i);
            }
        }
        return flag;
    }

    void traverse(int[][] graph, int v) {
        if (!flag) {
            return;
        }

        visited[v] = true;
        for (int u : graph[v]) {
            if (!visited[u]) {
                colors[u] = !colors[v];
                traverse(graph,u);
            }else {
                if (colors[u] == colors[v]) {
                    flag = false;
                    return;
                }
            }
        }
    }
}

二、886. 可能的二分法

题目链接:https://leetcode.cn/problems/possible-bipartition/
思路:和上一题类似,也是看看能否二分图,不过没给邻接表,自己构建一下邻接表,然后就是正常遍历判断是否是二分图

class Solution {
    boolean flag = true;
    boolean[] visited;
    boolean[] colors;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] graph = buildGraph(n, dislikes);
        visited = new boolean[n];
        colors = new boolean[n];
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                traverse(graph, i);
            }
        }
        return flag;
    }
    List<Integer>[] buildGraph(int n, int[][] dislikes) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] ints : dislikes) {
            graph[ints[0]-1].add(ints[1]-1);
            graph[ints[1]-1].add(ints[0]-1);
        }
        return graph;
    }
    void traverse(List<Integer>[] graph, int v) {
        if (!flag) {
            return;
        }
        visited[v] = true;
        for (Integer u : graph[v]) {
            if (!visited[u]) {
                colors[u] = !colors[v];
                traverse(graph, u);
            }else {
                if (colors[u] == colors[v]) {
                    flag = false;
                    return;
                }
            }
        }
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/135169918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。