当前位置: 首页 > news >正文

leetcode-判断二分图

. - 力扣(LeetCode)

存在一个 无向图 ,图中有 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

class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {unordered_set<int> a;unordered_set<int> b;for (int i = 0; i < graph.size(); i++) {auto& nodes = graph[i];if (a.find(i) != a.end()) {for (int j = 0; j < nodes.size(); j++) {if (a.find(nodes[j]) != a.end()) {return false;}if (b.find(nodes[j]) == b.end()) {b.insert(nodes[j]);}}                } else if (b.find(i) != b.end()) {for (int j = 0; j < nodes.size(); j++) {if (b.find(nodes[j]) != b.end()) {return false;}if (a.find(nodes[j]) == a.end()) {a.insert(nodes[j]);}}} else {a.insert(i);for (int j = 0; j < nodes.size(); j++) {if (a.find(nodes[j]) != a.end()) {return false;}if (b.find(nodes[j]) == b.end()) {b.insert(nodes[j]);}}}}return true;}
};
class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {int n = graph.size();vector<int> flags(n, 0);for (int i = 0; i < n; i++) {auto& nodes = graph[i];if (flags[i] == -1) {// in Afor (int j = 0; j < nodes.size(); j++) {if (flags[nodes[j]] == -1) {// in Areturn false;}flags[nodes[j]] = 1;// put in B}} else if (flags[i] == 1) {// in Bfor (int j = 0; j < nodes.size(); j++) {if (flags[nodes[j]] == 1) {// in Breturn false;}flags[nodes[j]] = -1;// put in A}                } else {flags[i] = -1;for (int j = 0; j < nodes.size(); j++) {if (flags[nodes[j]] == -1) {// in Areturn false;}flags[nodes[j]] = 1;// put in B}                }}return true;}
};
class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {int n = graph.size();vector<int> flags(n, 0);for (int i = 0; i < n; i++) {if (flags[i] == 0) {if (!isBipartite(i, 1, flags, graph)) {return false;}}}return true;}bool isBipartite(int curNode, int curFlag, vector<int>& flags, vector<vector<int>>& graph) {if (flags[curNode] != 0) {return flags[curNode] == curFlag;}flags[curNode] = curFlag;for (auto nextNode : graph[curNode]) {if (!isBipartite(nextNode, -curFlag, flags, graph)) {return false;}}return true;}
};

相关文章:

leetcode-判断二分图

. - 力扣&#xff08;LeetCode&#xff09; 存在一个 无向图 &#xff0c;图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph &#xff0c;其中 graph[u] 是一个节点数组&#xff0c;由节点 u 的邻接节点组成。形式上&#xff0c…...

算法day30 回溯6

332 重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必须从 JFK …...

分享three.js实现乐高小汽车

前言 Web脚本语言JavaScript入门容易&#xff0c;但是想要熟练掌握却需要几年的学习与实践&#xff0c;还要在弱类型开发语言中习惯于使用模块来构建你的代码&#xff0c;就像小时候玩的乐高积木一样。 应用程序的模块化理念&#xff0c;通过将实现隐藏在一个简单的接口后面&a…...

gpt的构造和原理

gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的&#xff01;比如“Q&#xff1a;xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中&#xff0c;文本序列&#xff08;可能包含问题和紧随其后的答案&#xff09;被视为一个整体输入到模型…...

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…...

K8S之Job和CronJob控制器

这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务&#xff0c;例如&#xff1a;对数据库备份&#xff0c;可以直接在k8s上启动一个mysqldump备份程序&#xff0c;也可以启动一个pod&#xff0c;这个pod…...

基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的基于个人需求和地域特色的外卖推荐系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&…...

哈佛大学商业评论 --- 第三篇:真实世界中的增强现实

AR将全面融入公司发展战略&#xff01; AR将成为人类和机器之间的新接口&#xff01; AR将成为人类的关键技术之一&#xff01; 请将此文转发给您的老板&#xff01; --- 本文作者&#xff1a;Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的&#xff0c;但大…...

华为ICT七力助推文化产业新质生产力发展

创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成&#xff0c;符合新发展理念的先进生产力质态&#xff1b;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能&#xff0c;新质生产力能够摆脱…...

FastGpt流程

1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本&#xff0c;在文本里面进行数据清洗&#xff08;以防知识库删除后&#xff0c;数据清洗失效&#xff09; 可以插图&#xff0c;将图片通过网页检查F12查看路径放进去 或者直接在csdn放&#xff0c;直接复制链接…...

怎么在UE游戏中加入原生振动效果

我是做振动触感的。人类的五感“视听嗅味触”&#xff0c;其中的“触”就是触觉&#xff0c;是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯&#xff0c;也是习以为常&#xff0c;很多人漠视了触感的价值。大家对触感的认知还远远不…...

【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】

前言&#xff1a; &#x1f49e;&#x1f49e;大家好&#xff0c;我是书生♡&#xff0c;今天的内容主要是Hadoop的后两个组件&#xff1a;MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 &#x1f49e;&#x1f49e;前路漫漫&…...

蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)

题目描述 给定一个数组 Ai&#xff0c;分别求其每个子段的异或和&#xff0c;并求出它们的和。 或者说&#xff0c;对于每组满足 1≤L≤R≤n 的 L&#xff0c;R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L&#xff0c;R 得到的结果加起来的值。 输入格式 输入…...

background背景图参数边渐变CSS中创建背景图像的渐变效果

效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变&#xff08;linear-gradient&#xff09;或径向渐变&#xff08;radial-gradient&#xff09;。以下是一个使用线性渐变作为背景图像 代码: background: linear-gradient(to top, rgba(255,255,255,0)…...

『大模型笔记』吴恩达:AI 智能体工作流引领人工智能新趋势

吴恩达:AI 智能体工作流引领人工智能新趋势 文章目录 一. 概述二. AI 智能体的设计模式2.1. 反思(Reflection)2.2. 使用工具(Tool use)2.3. 规划(Planning)2.4. 多智能体协作(Multi-agent collaboration)三. 最后总结四. 参考文献一. 概述 我期待与大家分享我在 AI 智能体方面…...

腾讯光子工作室群 一面 (30min)

问题&#xff1a; 你毕业是打算考研还是直接工作 深挖项目&#xff08;介绍、剖析遇到问题如何解决&#xff09;&#xff1a; 你在进行攻击的时候会不会有穿模的情况&#xff0c;怎么解决 为什么会造成卡顿&#xff08;多嘴说的&#xff09; 说说行为树和状态机之间的差别 …...

Linux的信号栈的实现(1)

作者 pengdonglin137@163.com 环境 Linux 6.5 + ARM64 概述 在前一篇文章中介绍了Linux系统中的几种栈以及它们之间的切换,进程在用户态和内核态会使用不同的栈,在用户态的主线程和其他线程都有各自的栈,此外进程在执行信号处理程序时也需要栈,那么这个栈来自哪呢? …...

Python学习笔记——heapq

堆排序 思路 堆排序思路是&#xff1a; 将数组以二叉树的形式分析&#xff0c;令根节点索引值为0&#xff0c;索引值为index的节点&#xff0c;子节点索引值分别为index*21、index*22&#xff1b;对二叉树进行维护&#xff0c;使得每个非叶子节点的值&#xff0c;都大于或者…...

搜索与图论——拓扑排序

有向图的拓扑排序就是图的宽度优先遍历的一个应用 有向无环图一定存在拓扑序列&#xff08;有向无环图又被称为拓扑图&#xff09;&#xff0c;有向有环图一定不存在拓扑序列。无向图没有拓扑序列。 拓扑序列&#xff1a;将一个图排成拓扑序后&#xff0c;所有的边都是从前指…...

linux CentOS7配置docker的yum源并安装

[TOC](这里写目录标题 配置yum源Docker的自动化安装一些其他启动相关的命令&#xff1a; 配置yum源 使用以下命令下载CentOS官方的yum源文件 wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 清除yum缓存 yum clean all 更新yum缓存…...

CCC 数字钥匙 Release 3:BLE/UWB与NFC融合的无钥匙进入系统解析

1. CCC数字钥匙Release 3的技术革新 想象一下这样的场景&#xff1a;你双手提着购物袋走向爱车&#xff0c;距离3米时车灯自动点亮&#xff0c;1.5米时车门悄然解锁&#xff0c;拉开车门的瞬间引擎已经启动——这就是CCC数字钥匙Release 3带来的无感化体验。作为车联网联盟&…...

Python开发环境搭建新选择:Miniconda-Python3.11镜像体验

Python开发环境搭建新选择&#xff1a;Miniconda-Python3.11镜像体验 1. 为什么选择Miniconda-Python3.11镜像 Python作为当今最流行的编程语言之一&#xff0c;其版本管理和环境隔离一直是开发者面临的挑战。传统的Python安装方式往往会导致&#xff1a; 系统Python版本与项…...

数据开发平台如何落地实操?数据开发平台核心价值是什么?

数据开发平台是企业数字化建设的核心载体&#xff0c;搭建合规高效的数据开发平台&#xff0c;才能打通数据流转全链路&#xff0c;而多数企业落地数据开发平台时&#xff0c;往往陷入流程混乱、效率低下的困境。开始之前给大家分享一份数字化全流程资料包:https://s.fanruan.c…...

神经高利贷:预支未来技能导致认知崩溃

在软件测试领域&#xff0c;从业者常面临一个隐形威胁&#xff1a;过度追求新技能而忽视认知极限&#xff0c;最终引发崩溃。这种现象被称为“神经高利贷”&#xff0c;即通过预支未来学习能力来应对当前挑战&#xff0c;结果导致认知资源枯竭、错误率飙升&#xff0c;甚至职业…...

企业级Java SMB客户端:jcifs-ng深度架构解析与实战指南

企业级Java SMB客户端&#xff1a;jcifs-ng深度架构解析与实战指南 【免费下载链接】jcifs-ng A cleaned-up and improved version of the jCIFS library 项目地址: https://gitcode.com/gh_mirrors/jc/jcifs-ng jcifs-ng是一个经过彻底重构和优化的Java SMB客户端库&am…...

医学影像组学实战:Pyradiomics YAML配置文件全解析(附完整示例)

医学影像组学实战&#xff1a;Pyradiomics YAML配置文件全解析&#xff08;附完整示例&#xff09; 在医学影像分析领域&#xff0c;特征提取是构建精准诊断模型的关键步骤。Pyradiomics作为开源的医学影像组学工具包&#xff0c;通过YAML配置文件提供了高度灵活的特征提取方案…...

Python实战:用Statsmodels搞定简单线性回归(附NO浓度预测案例)

Python实战&#xff1a;用Statsmodels搞定简单线性回归&#xff08;附NO浓度预测案例&#xff09; 在数据分析领域&#xff0c;线性回归是最基础却最实用的统计方法之一。无论你是市场分析师预测销售额&#xff0c;还是环境科学家研究污染物分布&#xff0c;掌握线性回归都能让…...

终极RPG Maker解密工具:3分钟学会提取游戏资源

终极RPG Maker解密工具&#xff1a;3分钟学会提取游戏资源 【免费下载链接】RPGMakerDecrypter Tool for extracting RPG Maker XP, VX and VX Ace encrypted archives. 项目地址: https://gitcode.com/gh_mirrors/rp/RPGMakerDecrypter 还在为RPG Maker加密文件无法提取…...

Yep应用商店优化终极指南:提升App Store排名与下载量的10个策略

Yep应用商店优化终极指南&#xff1a;提升App Store排名与下载量的10个策略 【免费下载链接】Yep Meet Genius 项目地址: https://gitcode.com/gh_mirrors/ye/Yep Yep是一款主打社交互动的移动应用&#xff0c;通过优化App Store展示内容和用户体验&#xff0c;可以显著…...

LabelMe企业级部署方案:多用户权限管理与审计

LabelMe企业级部署方案&#xff1a;多用户权限管理与审计 LabelMe是一款强大的图像标注工具&#xff0c;支持多边形、矩形、圆形等多种标注形式&#xff0c;广泛应用于计算机视觉领域的数据准备工作。在企业环境中部署LabelMe时&#xff0c;多用户权限管理与操作审计是确保数据…...