有向图判环(leetcode207,leetcode210)
有向图判环(leetcode207,leetcode210)
有向图判环
#include <iostream>
#include <vector>
using namespace std;struct graph {int V; // 顶点的数量vector<vector<int>> adj; // 邻接表数组graph(int x): V(x), adj(x) {}
};// 参数 graph 表示图,cur 表示当前顶点,vis 表示访问标记数组的引用,recStack 表示递归栈
bool dfs(graph &g, int cur, vector<bool> &vis, vector<bool> &recStack) {if (!vis[cur]) {vis[cur] = true; // 标记当前顶点为已访问recStack[cur] = true; // 将当前顶点加入递归栈for (int nbr : g.adj[cur]) {if (!vis[nbr] && dfs(g, nbr, vis, recStack)) // 如果邻接顶点未被访问,则递归调用 dfsreturn true;else if (recStack[nbr]) // 如果邻接顶点已经在递归栈中,则存在环return true;}}recStack[cur] = false; // 从递归栈中移除当前顶点return false;
}bool HasCycle(graph &g) {vector<bool> vis(g.V, false); // 初始化访问标记数组,所有顶点均未被访问vector<bool> recStack(g.V, false); // 初始化递归栈for (int cur=0; cur<g.V; cur++) {if (!vis[cur] && dfs(g, cur, vis, recStack))return true; }return false;
}int main() {int V = 4;graph g(V);g.adj[0].push_back(1);g.adj[0].push_back(2);g.adj[1].push_back(2);g.adj[2].push_back(3);// g.adj[2].push_back(0); // 有环:0->1->2->0// g.adj[3].push_back(3); // 有环:3->3if (HasCycle(g))cout << "有环" << endl;elsecout << "无环" << endl;return 0;
}
leetcode207
class Solution {
public:bool dfs(vector<vector<int>>& adj, int cur, vector<bool> &vis, vector<bool> &recStack) {if (!vis[cur]) {vis[cur] = true; // 标记当前顶点为已访问recStack[cur] = true; // 将当前顶点加入递归栈for (int nbr : adj[cur])if (!vis[nbr] && dfs(adj, nbr, vis, recStack)) // 如果邻接节点未访问且有环,返回 truereturn true;else if (recStack[nbr]) // 如果邻接顶点已经在递归栈中,则存在环return true;}recStack[cur] = false; // 从递归栈中移除当前顶点return false; // 没有检测到环}bool canFinish(int V, vector<vector<int>>& prerequisites) {vector<vector<int>> adj(V); // 构建图的邻接表表示for (const auto& pre : prerequisites)adj[pre[1]].push_back(pre[0]);vector<bool> vis(V, false); // 初始化访问标记数组,所有顶点均未被访问vector<bool> recStack(V, false); // 初始化递归栈for (int cur=0; cur <V; cur++)if (!vis[cur] && dfs(adj, cur, vis, recStack))return false; return true;}
};
leetcode210
class Solution {
public:bool dfs(vector<vector<int>>& adj, int cur, vector<bool>& vis, vector<bool>& recStack, stack<int>& topOrder) {if (!vis[cur]) {vis[cur] = true; // 标记为已访问recStack[cur] = true; // 标记为在递归栈中for (int nbr : adj[cur]) // 遍历当前节点的邻接节点if (!vis[nbr] && dfs(adj, nbr, vis, recStack, topOrder))return true; // 如果邻接节点未访问且有环,返回 trueelse if (recStack[nbr])return true; // 如果邻接节点在递归栈中,说明有环}recStack[cur] = false; // 从递归栈中移除当前节点topOrder.push(cur); // 将当前节点加入拓扑排序栈return false; // 没有发现环}vector<int> findOrder(int V, vector<vector<int>>& prerequisites) {vector<vector<int>> adj(V);for (const auto& pre : prerequisites) // 构建图的邻接表表示adj[pre[1]].push_back(pre[0]); vector<bool> vis(V, false); // 初始化访问标记数组,所有顶点均未被访问vector<bool> recStack(V, false); // 初始化递归栈stack<int> topOrder; // 用于存储拓扑排序结果for (int cur = 0; cur < V; cur++)if (!vis[cur] && dfs(adj, cur, vis, recStack, topOrder))return {}; // 如果发现环,返回空数组vector<int> result;while (!topOrder.empty()) { // 将栈中的元素弹出,得到拓扑排序result.push_back(topOrder.top());topOrder.pop();}return result;}
};
相关文章:
有向图判环(leetcode207,leetcode210)
有向图判环(leetcode207,leetcode210) 有向图判环 #include <iostream> #include <vector> using namespace std;struct graph {int V; // 顶点的数量vector<vector<int>> adj; // 邻接表数组…...
概率论得学习和整理25:EXCEL 关于直方图/ 频度图 /hist图的细节,2种做hist图的方法
目录 1 hist图的特点 2 hist的设置技巧:直接生成的hist图往往很奇怪不好用:因为横轴的分组不对 3 如何修改分组 4 设置开放边界,把长尾合并,得到hist图1 5 用原始表得到频数表 6 用上面的频数图做柱状图,再修改&…...
PHP8.4下webman直接使用topthink/think-orm
环境信息 操作系统win11php 8.4.1webman-framework ^1.6.8MySQL 8.4.3topthink/think-orm ^3.0 说明 PHP8.3以下版本 直接使用webman提供的webman/think-orm更方便。 PHP 环境换为 8.4 使用webman/think-orm 报了个错;所以换topthink/think-orm,根据文…...
【从零开始入门unity游戏开发之——C#篇04】栈(Stack)和堆(Heap),值类型和引用类型,以及特殊的引用类型string,垃圾回收( GC)
文章目录 知识回顾一、栈(Stack)和堆(Heap)1、什么是栈和堆2、为什么要分栈和堆3、栈和堆的区别栈堆 4、总结 二、值类型和引用类型1、那么值类型和引用类型到底有什么区别呢?值类型引用类型 2、总结 三、特殊的引用类…...
基于微信小程序的小区疫情防控ssm+论文源码调试讲解
第2章 程序开发技术 2.1 Mysql数据库 为了更容易理解Mysql数据库,接下来就对其具备的主要特征进行描述。 (1)首选Mysql数据库也是为了节省开发资金,因为网络上对Mysql的源码都已进行了公开展示,开发者根据程序开发需…...
第P2周:Pytorch实现CIFAR10彩色图片识别
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 目标 实现CIFAR-10的彩色图片识别实现比P1周更复杂一点的CNN网络 具体实现 (一)环境 语言环境:Python 3.10 编 译 器: …...
CTFHub 命令注入-综合练习(学习记录)
综合过滤练习 命令分隔符的绕过姿势 ; %0a %0d & 那我们使用%0a试试,发现ls命令被成功执行 /?ip127.0.0.1%0als 发现一个名为flag_is_here的文件夹和index.php的文件,那么我们还是使用cd命令进入到文件夹下 http://challenge-438c1c1fb670566b.sa…...
OpenCV目标检测 级联分类器 C++实现
一.目标检测技术 目前常用实用性目标检测与跟踪的方法有以下两种: 帧差法 识别原理:基于前后两帧图像之间的差异进行对比,获取图像画面中正在运动的物体从而达到目标检测 缺点:画面中所有运动中物体都能识别 举个例子…...
QT6 Socket通讯封装(TCP/UDP)
为大家分享一下最近封装的以太网socket通讯接口 效果演示 如图,界面还没优化,后续更新 废话不多说直接上教程 添加库 如果为qmake项目中,在.pro文件添加 QT network QT core gui QT networkgreaterThan(QT_MAJOR_VERS…...
elasticsearch设置密码访问
1 用户认证介绍 默认ES是没有设置用户认证访问的,所以每次访问时,直接调相关API就能查询和写入数据。现在做一个认证,只有通过认证的用户才能访问和操作ES。 2 开启加密设置 1.生成证书文件 /usr/share/elasticsearch/bin/elasticsearch-…...
彻底理解如何优化接口性能
作为后端研发,必须要掌握怎么优化接口的性能或者说是响应时间,这样才能提高系统的系能,本文通过如下两个方面进行分析: 一.后端代码 有如下几步: 1.缓存机制 这是最场景的方式,当使用了缓存后,…...
C# 位运算
一、数据大小对应关系 说明: 将一个数据每左移一位,相当于乘以2。因此,左移8位就是乘以2的8次方,即256。 二、转换 1、 10进制转2进制字符串 #region 10进制转2进制字符串int number1 10;string binary Convert.ToString(num…...
【Flink-scala】DataStream编程模型之状态编程
DataStream编程模型之状态编程 参考: 1.【Flink-Scala】DataStream编程模型之数据源、数据转换、数据输出 2.【Flink-scala】DataStream编程模型之 窗口的划分-时间概念-窗口计算程序 3.【Flink-scala】DataStream编程模型之窗口计算-触发器-驱逐器 4.【Flink-scal…...
RabbitMQ的核心组件有哪些?
大家好,我是锋哥。今天分享关于【RabbitMQ的核心组件有哪些?】面试题。希望对大家有帮助; RabbitMQ的核心组件有哪些? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 RabbitMQ是一个开源的消息代理(Messag…...
【Linux基础】基本开发工具的使用
目录 一、编译器——gcc/g的使用 gcc/g的安装 gcc的安装: g的安装: gcc/g的基本使用 gcc的使用 g的使用 动态链接与静态链接 程序的翻译过程 1. 一个C/C程序的构建过程,程序从源代码到可执行文件必须经历四个阶段 2. 理解选项的含…...
常见的数据结构和应用场景
数据结构是计算机科学中的基础概念,用于组织和存储数据,以便能够高效地访问和修改。下面是几种常见数据结构及其代表性应用场景: 1. 数组(Array) 问题解决:数组是一种线性数据结构,用于存储相…...
爬虫基础学习
爬虫概念与工作原理 爬虫是什么:爬虫(Web Scraping)是自动化地访问网站并提取数据的技术。它模拟用户浏览器的行为,通过HTTP请求访问网页,解析HTML文档并提取有用信息。 爬虫的基本工作流程: 发送HTTP请求…...
C++对象数组对象指针对象指针数组
一、对象数组 对象数组中的每一个元素都是同类的对象; 例1 对象数组成员的初始化 #include<iostream> using namespace std;class Student { public:Student( ){ };Student(int n,string nam,char s):num(n),name(nam),sex(s){};void display(){cout<&l…...
D96【python 接口自动化学习】- pytest进阶之fixture用法
day96 pytest的fixture详解(三) 学习日期:20241211 学习目标:pytest基础用法 -- pytest的fixture详解(三) 学习笔记: fixture(scop"class") (scop"class") 每一个类调…...
【算法】动态规划中01背包问题解析
📢博客主页:https://blog.csdn.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由 JohnKi 原创,首发于 CSDN🙉 📢未来很长&#…...
Llama-3.2-3B优化指南:Ollama性能调优,让模型跑得更快更稳
Llama-3.2-3B优化指南:Ollama性能调优,让模型跑得更快更稳 1. 为什么需要优化Llama-3.2-3B? Llama-3.2-3B作为一款30亿参数的轻量级大语言模型,在消费级硬件上表现出色。但在实际部署中,很多用户会遇到性能瓶颈&…...
FUTURE POLICE语音模型Agent智能体开发:多轮语音对话任务规划
FUTURE POLICE语音模型Agent智能体开发:多轮语音对话任务规划 想象一下,你对着手机说:“帮我订一张下周五从北京飞往上海,下午出发的机票,要经济舱。” 几秒钟后,手机用自然的人声回复你:“好的…...
PasteMD免配置环境:Docker镜像封装,3条命令完成私有化AI格式化服务部署
PasteMD免配置环境:Docker镜像封装,3条命令完成私有化AI格式化服务部署 1. 项目简介:剪贴板智能美化工具 PasteMD是一个完全私有化的AI文本格式化工具,它基于Ollama本地大模型运行框架和强大的llama3:8b模型构建。这个工具的核心…...
2026年三维扫描仪选购指南:专业厂家如何选,这几点是关键
在工业4.0与智能制造浪潮的推动下,三维扫描技术已成为产品设计、逆向工程、质量检测等领域的核心工具。面对市场上琳琅满目的品牌与型号,如何选择一台真正适合自身需求、性能可靠的三维扫描仪,成为众多工程师、设计师和企业决策者面临的难题。…...
Phi-4-mini-reasoning应用场景:数学建模竞赛辅助推导与公式生成
Phi-4-mini-reasoning应用场景:数学建模竞赛辅助推导与公式生成 1. 模型概述与核心能力 Phi-4-mini-reasoning是一款由微软开发的轻量级开源模型,专为数学推理、逻辑推导和多步解题等强逻辑任务设计。这个3.8B参数的模型虽然体积小巧,但在数…...
3个核心模块揭秘:Python量化投资如何免费获取通达信专业数据
3个核心模块揭秘:Python量化投资如何免费获取通达信专业数据 【免费下载链接】mootdx 通达信数据读取的一个简便使用封装 项目地址: https://gitcode.com/GitHub_Trending/mo/mootdx 你是否在量化投资中为数据获取而烦恼?商业接口太贵,…...
PIPAL数据集实战:如何用Elo评分系统提升图像质量评估的准确性
PIPAL数据集实战:如何用Elo评分系统提升图像质量评估的准确性 在计算机视觉领域,图像质量评估(IQA)一直是算法研发的关键环节。随着生成对抗网络(GAN)等技术的突破,传统IQA方法逐渐暴露出局限性…...
别再手动写Excel了!用Coze+GPT-4o,5分钟把Word需求文档变成测试用例表格
从Word到Excel:零代码打造智能测试用例生成流水线 每次产品需求文档更新后,测试团队最头疼的莫过于手动编写成百上千条测试用例。传统方式下,测试工程师需要反复阅读PRD文档,逐条提取功能点,再按照固定模板填充到Excel…...
快速上手语音情感分析:Emotion2Vec+系统参数配置与结果解读
快速上手语音情感分析:Emotion2Vec系统参数配置与结果解读 1. 系统概述与核心价值 Emotion2Vec Large语音情感识别系统是一款基于深度学习的语音分析工具,能够自动识别语音中蕴含的情感状态。该系统由科哥团队基于阿里达摩院ModelScope平台的原始模型进…...
Omni-Vision Sanctuary在嵌入式边缘设备上的轻量化部署思考
Omni-Vision Sanctuary在嵌入式边缘设备上的轻量化部署思考 1. 嵌入式视觉的挑战与机遇 在智能摄像头、工业质检设备、无人机等嵌入式场景中,视觉模型的部署一直面临特殊挑战。传统方案要么性能不足,要么功耗过高,难以平衡实时性与能效比。…...
