hdoj-3342-Legal or Not(拓扑排序)
2024-09-01 03:16:31
/*
Name:hdoj-3342-Legal or Not
Copyright:
Author:
Date: 2018/4/11 15:59:18
Description:
判断是否存在环
*/
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e+;
int du[MAXN], n , m, L[MAXN];
vector<int> g[MAXN];
bool topsort() {
memset(du, , sizeof(du));
for (int i=; i<n; i++) {
for (int j=; j<g[i].size(); j++) {
du[g[i][j]]++;
}
}
int tot = ;
queue<int> Q;
for (int i=; i<n; i++) {
if (!du[i]) {
Q.push(i);
}
}
while (!Q.empty()) {
int x = Q.front();
Q.pop();
L[tot++] = x;
for (int j=; j<g[x].size(); j++) {
int t = g[x][j];
du[t]--;
if (!du[t]) {
Q.push(t);
}
}
}
if (tot == n) return ;
return ;
}
int main()
{
while (cin>>n>>m && (m || n)) {
memset(L, , sizeof(L));
memset(g, , sizeof(g));
for (int i=; i<m; i++) {
int a, b;
cin>>a>>b;
g[a].push_back(b);
}
if (topsort() == ) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}
最新文章
- HotApp小程序服务范围资质查询器
- 关于js单线程(转载)
- JavaScript Array 常用函数整理
- ubuntu下的时间设定(硬件时间,系统时间,本地时间)
- html中相似的标签、属性的区别
- C# 将DataTable存储到DBF文件中
- 自然数的K次幂的数列求和
- cssTex
- OSFM Tables
- JavaWeb学习笔记--2.3内置对象
- Erlang语言介绍
- asp-net-web-api 自定义URl插件
- 团队作业4----第一次项目冲刺(Alpha版本)4.24
- eclipse弃坑记第一篇之在idea上配置Tomcat环境并创建Javaweb项目的详细步骤原创
- Git 使用vi或vim命令打开、关闭、保存文件
- 鸟哥Linux私房菜基础学习篇学习笔记2
- linux下ls -l命令(即ll命令)查看文件的显示结果分析
- I2C的小结
- 【Codeforces 912E】Prime Gift
- javascript 获取节点元素的封装