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 == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1graph[u]不会包含ugraph[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-判断二分图
. - 力扣(LeetCode) 存在一个 无向图 ,图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ,其中 graph[u] 是一个节点数组,由节点 u 的邻接节点组成。形式上,…...
算法day30 回溯6
332 重新安排行程 给你一份航线列表 tickets ,其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK …...
分享three.js实现乐高小汽车
前言 Web脚本语言JavaScript入门容易,但是想要熟练掌握却需要几年的学习与实践,还要在弱类型开发语言中习惯于使用模块来构建你的代码,就像小时候玩的乐高积木一样。 应用程序的模块化理念,通过将实现隐藏在一个简单的接口后面&a…...
gpt的构造和原理
gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的!比如“Q:xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中,文本序列(可能包含问题和紧随其后的答案)被视为一个整体输入到模型…...
基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展,计算机的应用日渐成熟,其强大的功能给人们留下深刻的印象,它已经应用到了人类社会的各个层次的领域,发挥着重要的不可替换的作用。信息管理作为计算…...
K8S之Job和CronJob控制器
这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务,例如:对数据库备份,可以直接在k8s上启动一个mysqldump备份程序,也可以启动一个pod,这个pod…...
基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。
演示视频: 基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构&…...
哈佛大学商业评论 --- 第三篇:真实世界中的增强现实
AR将全面融入公司发展战略! AR将成为人类和机器之间的新接口! AR将成为人类的关键技术之一! 请将此文转发给您的老板! --- 本文作者:Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的,但大…...
华为ICT七力助推文化产业新质生产力发展
创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成,符合新发展理念的先进生产力质态;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能,新质生产力能够摆脱…...
FastGpt流程
1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本,在文本里面进行数据清洗(以防知识库删除后,数据清洗失效) 可以插图,将图片通过网页检查F12查看路径放进去 或者直接在csdn放,直接复制链接…...
怎么在UE游戏中加入原生振动效果
我是做振动触感的。人类的五感“视听嗅味触”,其中的“触”就是触觉,是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯,也是习以为常,很多人漠视了触感的价值。大家对触感的认知还远远不…...
【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】
前言: 💞💞大家好,我是书生♡,今天的内容主要是Hadoop的后两个组件:MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 💞💞前路漫漫&…...
蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)
题目描述 给定一个数组 Ai,分别求其每个子段的异或和,并求出它们的和。 或者说,对于每组满足 1≤L≤R≤n 的 L,R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L,R 得到的结果加起来的值。 输入格式 输入…...
background背景图参数边渐变CSS中创建背景图像的渐变效果
效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变(linear-gradient)或径向渐变(radial-gradient)。以下是一个使用线性渐变作为背景图像 代码: 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)
问题: 你毕业是打算考研还是直接工作 深挖项目(介绍、剖析遇到问题如何解决): 你在进行攻击的时候会不会有穿模的情况,怎么解决 为什么会造成卡顿(多嘴说的) 说说行为树和状态机之间的差别 …...
Linux的信号栈的实现(1)
作者 pengdonglin137@163.com 环境 Linux 6.5 + ARM64 概述 在前一篇文章中介绍了Linux系统中的几种栈以及它们之间的切换,进程在用户态和内核态会使用不同的栈,在用户态的主线程和其他线程都有各自的栈,此外进程在执行信号处理程序时也需要栈,那么这个栈来自哪呢? …...
Python学习笔记——heapq
堆排序 思路 堆排序思路是: 将数组以二叉树的形式分析,令根节点索引值为0,索引值为index的节点,子节点索引值分别为index*21、index*22;对二叉树进行维护,使得每个非叶子节点的值,都大于或者…...
搜索与图论——拓扑排序
有向图的拓扑排序就是图的宽度优先遍历的一个应用 有向无环图一定存在拓扑序列(有向无环图又被称为拓扑图),有向有环图一定不存在拓扑序列。无向图没有拓扑序列。 拓扑序列:将一个图排成拓扑序后,所有的边都是从前指…...
linux CentOS7配置docker的yum源并安装
[TOC](这里写目录标题 配置yum源Docker的自动化安装一些其他启动相关的命令: 配置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缓存…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
UE5 音效系统
一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类,将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix,将上述三个类翻入其中,通过它管理每个音乐…...
