HDU.3342 Legal or Not (拓扑排序 TopSort)
2024-08-25 15:11:50
HDU.3342 Legal or Not (拓扑排序 TopSort)
题意分析
裸的拓扑排序 根据是否成环来判断是否合法
详解请移步
算法学习 拓扑排序(TopSort)
代码总览
#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#define nmax 200
#define MEM(x) memset(x,0,sizeof(x))
using namespace std;
int n,m;
int indegree[nmax];
vector<int> v[nmax];
bool suc = true;
void topsort()
{
int cnt = 0;
queue<int> q;
while(1){
for(int i = 0; i<n; ++i){
if(indegree[i] == 0){
q.push(i);
cnt++;
indegree[i] = -1;
}
}
if(q.empty()) break;
while(!q.empty()){
int t = q.front();q.pop();
for(int i = 0; i<v[t].size();++i){
int tt = v[t][i];
if(indegree[tt] == -1){
suc =false;
break;
}else
indegree[tt]--;
}
if(!suc) break;
}
if(!suc) break;
}
if(suc && cnt!=n) suc = false;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&m) == 2 && n){
MEM(indegree);
suc = true;
for(int i = 0; i<n;++i) v[i].clear();
for(int i = 0; i<m; ++i){
int a,b;
scanf("%d%d",&a,&b);
indegree[b]++;
v[a].push_back(b);
}
topsort();
printf("%s\n",suc?"YES":"NO");
}
return 0;
}
最新文章
- Devexress XPO xpPageSelector 使用
- 什么是java path环境变量
- 16.检查是否为BST
- HDU5900
- MySQL &#183; 性能优化 &#183; 条件下推到物化表
- angular 自定义指令 link
- Redis 一:安装篇
- Invalid embedded descriptor for ";.proto";.Dependencies passed (Protobufer)解决办法
- html网页特殊符号代码
- Java Des加解密方法(c#加密Java解密)
- Unix代码段和数据段
- 微信企业付款获取RSA
- Spring Boot – 自定义PropertyEditor
- C#中as运算符
- Confluence 6 你模板中可用的对象
- 磁盘修改AF
- wriesharek同时监听多个端口
- 19/03/30Python笔记
- 函数式编程编程即高阶函数+monad
- Centos 创建 docker项目