当前位置: 首页 > 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缓存…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...