HDU 3342 Legal or Not【拓扑排序】
2024-09-02 01:29:00
题意:给出n,m,人的编号为 0到n-1,再给出m个关系,问能不能够进行拓扑排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int indegree[1005],queue[1005],head[1005];
struct Edge
{
int to;
int next;
} edge[1005];
int main()
{
int n,m,i,j,k,iq,a,b;
while(scanf("%d %d",&n,&m)!=EOF&&n&&m)
{
memset(head,-1,sizeof(head));
memset(indegree,0,sizeof(indegree));
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
edge[i].to=b;
edge[i].next=head[a];
head[a]=i;
indegree[b]++;
}
iq=0;
for(i=0;i<n;i++)
{
if(indegree[i]==0)
{
queue[iq++]=i;
}
} for(i=0;i<iq;i++)
{
for(k=head[queue[i]];k!=-1;k=edge[k].next)
{
indegree[edge[k].to]--;
if(indegree[edge[k].to]==0)
{
queue[iq++]=edge[k].to;
}
}
}
if(iq==n) printf("YES\n");
else
printf("NO\n");
}
}
最新文章
- 看JVM就推荐这本书
- noip2008 双栈排序
- Android中Java与JavaScript之间交互(转)
- css 设计总结
- jQuery基础 -- 如何判断页面元素存在与否
- Groovy basic
- 上传图片shell绕过过滤的方法
- js认清this的第一步
- Activity Lifecycle
- PHP字符串拼接与MySQL语句
- linux文件操作命令--转
- Visual Assist X 快捷键
- windbg源码驱动调试 + 无源码驱动调试
- cocos开发插件笔记
- 函数作用域之闭包与this!
- 29.如何不用 transition 和 animation 也能做网页动画
- ios之两个view传值
- struts+spring+hibernate两张表字段名一样处理方法
- Jquery 技术小结
- bzoj4144【AMPPZ2014】Petrol