草庐IT

leetcode 785. Is Graph Bipartite判断二分图 (中等)

okokabcd 2023-03-28 原文

一、题目大意

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

输出：false

解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]

输出：true

解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

提示：

  • graph.length == n

  • 1 <= n <= 100

  • 0 <= graph[u].length < n

  • 0 <= graph[u][i] <= n - 1

  • graph[u] 不会包含 u

  • graph[u] 的所有值 互不相同

  • 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/is-graph-bipartite
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

利用队列和广度优先搜索，我们可以对未染色的节点进行染色，并且检查是否有颜色相同的相邻节点存在，在代码中我们用0表示未检查的节点，用1和2表示两种不同的颜色

三、解题方法

3.1 Java实现

public class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        if (n == 0) {
            return true;
        }
        int[] color = new int[graph.length];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                q.push(i);
                color[i] = 1;
            }
            while (!q.isEmpty()) {
                int node = q.pop();
                for (int j : graph[node]) {
                    if (color[j] == 0) {
                        q.push(j);
                        color[j] = color[node] == 2 ? 1 : 2;
                    } else if (color[node] == color[j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

四、总结小记

  • 2022/10/11 下面开启图的进程；读到一段话挺有感触的：站在生命的高度看待生活，站在结局的角度看待开始
二分Bipartitegraph无向li算法与数据结构

有关leetcode 785. Is Graph Bipartite判断二分图 (中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. 机器学习——时间序列ARIMA模型(四)：自相关函数ACF和偏自相关函数PACF用于判断ARIMA模型中p、q参数取值 - 2

    文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk​=Var(yt​)Cov(yt​,yt−k​)​其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  4. 如何判断oracle是否启动及启动oracle数据库 - 2

    plsql连接Oracle超时，完犊子了肯定是服务器断电了。得马上检查Oracle服务器状态1、检查数据库是否启动su-oracle切换到Oracle用户，输入sqlplus/assysdba显示连接状态。如果末尾显示的状态是Connectedtoanidleinstance.证明未启动2、启动数据库startup启动数据库，末尾出现Databaseopened说明数据库启动成功3、查看数据库监听是否正常先quit;断开Oracle连接，使用lsnrctlstatus查看监听状态，如果出现TNS-开头的Nolistener、Connectionrefused等错误，说明监听未启动4、启动数据库

  5. 【Python】判断字符串输入合法化 - 2

    Python判断字符串输入合法化只包含数字包含数字只包含中文包含中文只包含字母包含字母只包含数字判断字符串是否只包含数字：1.str.isdecimal()如果str只包含全角数字则返回True2.str.isdigit()如果str只包含全角数字、unicode编码的数字字符串例如⑴、\u00b2此类型则返回True3.str.isnumeric()如果str只包含数字（全角、半角）则返回True包含数字判断字符串是否只包含数字：print(bool(re.search(r'\d',"12321sad")))re.search()方法扫描整个字符串，并返回第一个成功的匹配，(re.searc

  6. ruby-on-rails - 如何判断 Rails Action 邮件发送是否失败？ - 2

    在我的项目中，我使用的是Rails4.1.1和Ruby2.1.1。我正在阅读mailgem，但不确定如何检查deliver是否失败(出于任何原因)。result=UserMailer.signup.deliverifresult.action=='failed'orresult.bounced?#Howcanyoutellifadeliverhasfailed?#Dostuffhereiffailedend 最佳答案 如http://guides.rubyonrails.org/action_mailer_basics.html中所

  7. ruby - 如何使用 ruby​​ 判断 FTP 文件是否存在？ - 2

    我正在尝试找出判断文件是否存在于ftp服务器上的最佳和最快的方法。这是我想出的...defremote_exists?(idx)#@file.rewindif@file.eof?ftp=Net::FTP.new(FTP_SERVER)ftp.loginbeginftp.size(idx)rescueExceptionreturnfalseendtrueend似乎只捕获每个异常不是一个好主意，但我在获取正确的特定异常时遇到了麻烦。我也在使用OpenURI在我的代码中实际获取文件。我试图弄清楚是否有一些更好的方法，但我认为它只是使用Net::FTP。 最佳答案

  8. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  9. ruby-on-rails - 如何判断缓存是否正常工作。 rails 4 - 2

    我正在阅读“使用Rails4进行敏捷Web开发”指南，并来到了有关缓存的部分。以下是要遵循的步骤:在config/environments/development.rb中config.action_controller.perform_caching=true在app/models/product.rb中defself.latestProduct.order(:updated_at).lastend在views/store/index.html.erb中为了验证现金是否有效，该书说:“就验证它是否有效而言，不幸的是，没有太多可看的东西。如果你去那个页面，你应该看不到任何变化，这实际上是

  10. ruby-on-rails - 在 Ruby 中有没有办法判断方法的定义位置？ - 2

    在Ruby中有没有一种方法可以判断方法的定义位置？我正在浏览ruby​​-guides并且有一行代码显示为Post.all我怎么知道all是在哪里定义的？ 最佳答案 如果你想知道定义方法的文件和行，使用Post.method(:all).source_location它会给你[file,line]或者nil如果它是一个C方法。 关于ruby-on-rails-在Ruby中有没有办法判断方法的定义位置？，我们在StackOverflow上找到一个类似的问题： h

随机推荐