用拓扑排序检测有向图中是否有环
目录
算法主要步骤
代码
测试数据
提示：由于拓扑排序的检测方式不涉及到边权或点权，所以拓扑序列中的正环和负环都能够被检测出来。检测可达负环可以用Bellman-Ford或者SPFA。
算法主要步骤
1. 记录每个结点的入度，设置一个队列，专门存放入度为0的结点，设置一个整型计数变量inqNum，记录加入过队列的结点的个数。
2. 首先将所有的入度为0的点放入队列中，进入while循环，条件是队列不为空，对于队列中的每一个点，都对齐后继结点的入度进行减一操作，如果在那之后该后继节点的入度变为0，则将其加入队列。
3. 注意inqNum的维护，不是在将一个结点放入队列时增加，而是在它弹出后、处理了它的所有后继节点后增加，这样只要写一处代码。出了while循环后对inqNum进行判断，如果恰好等于节点个数说明图中没有环，否则说明有环(环上的结点由于永远不会入度为0所以入不了队列)
代码
#include<cstdio>
#include<algorithm>
#include<queue>using namespace std;const int maxn = 1010;int vNum;
vector<int> G[maxn];
int inDegree[maxn] = {0};//记录每个点的入度
int inqNum = 0;bool topoSort(){queue<int> Q;for(int i=0;i<vNum;i++){if(inDegree[i]==0){Q.push(i);}}while(!Q.empty()){int u = Q.front();Q.pop();for(int i=0;i<G[u].size();i++){int v = G[u][i];inDegree[v] --;if(inDegree[v]==0){Q.push(v); }}inqNum ++;}if(inqNum==vNum)return true;else return false;
}int main(){int eNum;scanf("%d %d",&vNum,&eNum);int v1,v2;while(eNum--){scanf("%d %d",&v1,&v2);inDegree[v2] ++;//v2不会是起点了 G[v1].push_back(v2);}if(topoSort())printf("该拓扑结构不含有环");else printf("该拓扑结构含有环"); return 0;
}测试数据
第一行是点的个数(从0开始编号)、边的个数
后面是拓扑序列
#Case 1 无环
8 15
0 1
1 2
3 4
3 7
4 5
7 5
5 6
0 4
3 1
1 4
1 5
2 4
7 2
2 5
2 6# Case 2 有环
4 5
0 1
1 2
3 0
3 2
2 0相关文章：
关于大型网站技术演进的思考（五）--存储的瓶颈（5）
上文里我遗留了两个问题，一个问题是数据库做了水平拆分以后，如果我们对主键的设计采取一种均匀分布的策略，那么它对于被水平拆分出的表后续的查询操作将有何种影响，第二个问题就是水平拆分的扩容问题。这两个问题在深入下去&#…
Project Chameleon Work In Progress 10
现在的进展是，UMDF驱动的DeviceIOControl和Read、Write已经都能使用了，并且FX2LP的EP6IN也正常工作，下面是工作中的测试代码截图： 转载于:https://www.cnblogs.com/skogkatt/archive/2010/03/13/4163356.html
maven项目中 把依赖的jar包一起打包
2019独角兽企业重金招聘Python工程师标准>>> Maven1-HelloWorld简单入门 使用Maven Assembly plugin将依赖打包进jar 1、pom.xml 配置文件： 在pom.xml配置文件中添加 <build> <plugins> <plugin> <artifactId>maven-assembly…
PAT（甲级）2019年春季考试 7-4 Structure of a Binary Tree
目录 整体思路 犯的错误 代码 整体思路 1.先根据后序和中序序列建树，老生常谈，记得返回root 2.对树进行BFS，在这个过程中用hash的方式记录下每个值对应的父节点、左孩子、右孩子的值，记录下深度(即层数)，还有孩子…
vs2008 常用快捷键
编辑快捷键 CtrlB,T 切换书签开关 CtrlB,N 移动到下一书签 CtrlB,P 移动到上一书签 CtrlB,C 清除全部标签 CtrlI 渐进式搜索 CtrlShiftI反向渐进式搜索 F12 转到定义 AltF12 查找符号(列出所有查找结果) CtrlF 查找 CtrlH 替换 CtrlShi…
我理解的观察者模式
什么是观察者模式？ 当对象间存在一对多关系时,比如，当一个对象被修改时，则会自动通知它的依赖对象。观察者模式也叫做发布订阅模式。 观察者模式有什么好处？ 观察者模式中，被观察者发生改变时，会自动通知所…
PAT（甲级）2019年春季考试 7-3 Telefraud Detection
1. 这题复杂在诈骗检测算法的理解 怎样的一个人会被判定成嫌疑犯呢？ 他打出给别人的累计通话时长的不同的人数大于K 注意：不同和累计 怎样的两个人会被判定成同伙呢？ 相互之间有通话记录 2. 同伙的合并我采用的并查集，在设置…
Linux基础命令---diffstat
diffstat这个程序读取diff的输出，并显示每个文件的插入、删除和修改的直方图。Diffstat是一个用于检查大型复杂修补程序文件的程序。它从包含diff输出的一个或多个输入文件中读取，生成针对引用的每个文件更改的总行的直方图。如果输入文件名以.bz 2、.gz…
两个asp.net发送邮件类
代码 //第一个usingSystem;usingSystem.Text;usingSystem.Net.Mail;namespaceCars.Tootls.Tools{ publicclassEmail { privateEmail() { } ///<summary>///发送邮件 ///</summary>///<param name"Su…
symfony2是什么？
首先，symfony2是一个松散的，独立的，有组织严密的php组件的集合，它可以为你解决一些web开发中一般性的问题。 其次，基于这些组件，php又可以作为一个独立web框架使用。 转载于:https://www.cnblogs.com/ljcph…
PAT（甲级）2019年春季考试 7-2 Anniversary
注意点 1. 记录是不是校友，有两种方法 （1）map<string,int> mp mo[guest] 1 判断mp[comer] （2）set<string> st st.insert(guest) st.count(comer) 2. 由于只需要输出年龄最大的&…
根据总用量计算每种包装规格的购买量和总价
最近有这么一个需求，就是给出客户需要的总量，然后根据数据库记录的包装规格，计算出客户需要购买的包装规格种类和个数，而且要保证客户的花费最小。 示例图片效果 示例代码实现如下。欢迎大家一起讨论。 代码 using System;using S…
5个在线调试代码的网站
对于编程开发的人来说，有个快速测试代码的地方是非常方便重要的，这里，我们收集了5个很好用的在线调试网站。 1.codepad 是一款简单的在线 IDE 编辑器服务，你只需要把代码粘贴进去就可以编译运行了，连工程也不需要新建&…
Windows 日志高级筛选实践
背景经常需要查看日志，不仅是用来排错，有些时候我还需要监控系统来抓取特定日志来帮助减少我的工作负担，以及时监控到异常出现，并作出通知及响应，那么从大量日志中快速并精确筛选出想要的日志，并且精确提取…
PAT（甲级）2018年秋季考试 7-1 Werewolf - Simple Version
1. 我设置了一个结构体变量存储每个人的指控信息 struct IF{int type 0;int no; }; 这里我发现了一件事，如果结构体只有有参数的构造函数，那么直接声明该结构体类型的数组是不行的。但是好处是数组知道下标可以直接赋值。 也就是这样组合最好&#x…
appium 启动失败解决方案
本机下载了：AppiumForWindows，启动Appium.exe 的时候，立即提示：应用程序已停止运行！！ 本机环境： WIN 7 64 位，后来查了资料才知道Appium 要求安装.net framework 4.5，本机…
Django基础-数据分页
2019独角兽企业重金招聘Python工程师标准>>> pager.py # -*- coding:utf8 -*- """ 引用说明： 数据总个数：total_count 数据总页数：num_pages 每页显示的行数：perPageItemNum【默认显示10行】 最多显示页…
存货的计划属性设置（ATO模型和PTO模型）
对于原来应用ERP1时已经存在的存货，如果在存货属性中没有进行过设置或者设置不完善，需要进行补充设置。这样的补充设置包括： 自制：具有该属性的存货可由企业生产自制。如工业企业生产的产成品、半成品等存货。具有该属性的存货可用…
(C++)判断一个序列是non-increasing/non-decreasing还是两者都不的两个方法
思路：根据前两个值预设类型，再遍历后面的pair，看是否推翻预设 int judgeType(vector<int> vi){//-1 递减 0 啥也不是 1 递增 if(vi.size()1)return 0;//根据前两个元素的大小设置初始类型int type;if(vi[1]>vi[0])type 1;else …
java 下载文件功能代码例子
public static void down(HttpServletRequest request, HttpServletResponse response) throws Exception { String name"aaa.*";//文件名 String uploadPath UploadFileHelper.getRepositoryPath()"//";//文件来源 String filePath…
不要小看字符串
字符串非常非常常见又重要，而且还有那么多名堂在里面 字符串: 在标准C中，是没有字符串变量的，但是有字符数组。而且标准C带有的标准库函数：string.h中包含了大量的字符串操作函数，当然如果必要的话，你也可以…
零基础学习Python需要注意的几个点，Python培训机构排名
俗话说的好万事开头难，不管你做任何事情，开头的确很较难的，学Python编程也是如此，因此刚开始学Python编程的同学们，就要多借鉴过来人的经验，少走弯路，本文小编就为大家分享几个Python编程小白初…
PAT（甲级）2018年冬季考试 7-4 Heap Paths(非递归与递归解法)
非递归解法 1. 前置知识：完全二叉树的属性 1.1 从1开始存储，子节点的下标除以二得到的是父节点的下标 1.2 数组的存放顺序刚好是层序遍历顺序 1.3 从1开始存储，节点的下标i和结点总数n如果满足 i*2>n说明该结点是叶子结点 2. 思路&am…
Request Connection: Remote Server @ 192.229.145.200:80
录制Loadrunner脚本时，提示：Request Connection: Remote Server 192.229.145.200:80 NOT INTERCEPTED!(REASON: User requested to IGNORE connection)；解决方法：1. 打开IE里的Internet选项，单击连接选项卡。单击最…
抽象工厂与工厂模式例子
NativeFactory。java package com;//定义 人有杀日本人 和 杀美国人两个方法interface NativePerson{ public void killAmeria(); public void killJapan();}//中国人实现了人的接口 class NativeChinese implements NativePerson{ //中国人杀美国人 public void killAmeria() …
《疯狂Java讲义》学习笔记（十）异常处理
2019独角兽企业重金招聘Python工程师标准>>> 0、Java的异常体系 1、异常概述 异常机制已经成为判断一门编程语言是否成熟的标准，目前主流的编程语言都提供了成熟的异常机制，增加了异常处理机制后的程序有更好的容错性，更加健壮 Ja…
PAT（甲级）2018年冬季考试 7-1 Google Recruitment
1. 本题是 substrsscanf的绝佳实践。 2. 判断素数使用i*i<n与i<(int)sqrt(0.1*x)的区别是前者可能再n接近10的9次方时溢出，但本题不会。 3. 尽管把字符串转变成了整数，但输出时仍旧输出字符串，如果选择打印整数，会遇到%0K…
MySQL 的“root”用户修改密码
MySQL 的“root”用户默认状态是没有密码的，所以在 PHP 中您可以使用 mysql_connect("localhost","root","") 来连接 MySQL 服务器；如果您想为 MySQL 中的“root”用户设置密码，请在控制台中使用“mysqladmin”…
游戏AI之初步介绍（0）
目录 游戏AI是什么？游戏AI和理论AI智能的假象（更新）游戏AI和机器学习介绍一些游戏AI4X游戏AI《求生之路》系列角色扮演/沙盒游戏中的NPC游戏AI 需要学些什么？自治智能体群体智能感知状态机（重要）行为树&…
Google Adsense实用防踢技巧总结
我们都知道，对个人草根站长来说，Google AdSense是网站收入的主要来源之一，我在这里介绍一些常用的技巧。 希望通过这些技巧能够增加大家的Google AdSense收入，并防止自己的帐号被删除。大家喜欢的话就顶下吧！ 广告的位…