hdoj 3342 Legal or Not

Legal or Not


Problem Description

ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not. Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.

Input

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.

Output

For each test case, print in one line the judgement of the messy relationship.
If it is legal, output "YES", otherwise "NO".

Sample Input

3 2
0 1
1 2
2 2
0 1
1 0
0 0
 

Sample Output

YES
NO
 

题意:有N个人编号从0到N-1,给出M组师徒关系即a是b师徒。问你 这N个人之间 存不存在  师徒辈分混乱的情况。

这是一道简单的拓扑排序问题,考察就是排序中出现成环的情况,题目不难,看到题,很快就写出来了,但是有一点坑,就是要提前跳出加一个break;哎考虑问题不深入,这就是教训呀,不过终于发现了这个错误。。。


#include<cstdio>
#include<cstring>
int map[110][110],indegree[110];
void tuop(int n)
{
	int i,j,ans,flag=1;
	for(i=0;i<n;i++)
	{
		ans=-1;
		for(j=0;j<n;j++)
		{	
			if(indegree[j]==0)
			{	
				ans=j;
				break;
			}
		}	
		indegree[ans]=-1;
		if(ans==-1)
			break;
		for(j=0;j<n;j++)
		{
			if(map[ans][j])
				indegree[j]--;	
		}
	}
	if(ans>=0)
			printf("YES\n");
		else
			printf("NO\n");
}
int main()
{
	int m,n,a,b,i;
	while(scanf("%d%d",&n,&m),n)
	{
		memset(map,0,sizeof(map));
		memset(indegree,0,sizeof(indegree));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			if(map[a][b]==0)
			{
				map[a][b]=1;
				indegree[b]++;
			}
		}
		tuop(n);
	}
	return 0;
}


更多相关文章
  • Arista Networks公司与VMware公司日前宣布建立战略合作关系,促进客户在软件定义数据中心环境中(SDDC)加速采用网络虚拟化.基于双方在开发创新型综合SDDC解决方案领域长达四年的良好合作,两家公司签订了此项全新合作协议,主要用于VMware NSX™重点开发与共同推广公开发售的Ar ...
  • 1.2 你数据结构怎么学的?        早先我有一个学生叫蔡遥,绰号"小菜".他前段时间一直通过E-mail与我交流,其中说起了他工作的一些经历,感慨万千.我在这里就讲讲小菜的故事.        他告诉我,在做我学生时,其实根本就没好好学数据结构,时常逃课,考试也是临时突击 ...
  • http://github.ibireme.com/github/list/ios/ 网友整理的 ios 一些框架和 源码整理. 安装Ruby http://ruby.taobao.org/
  • 参考消息网7月28日报道 港媒称,一名西班牙旅客游览津巴布韦国家公园期间,以5万欧元利诱公园导游"睁一眼闭一眼",让他一尝狩猎狮子的乐趣.结果该园明星狮子遭攻击惨死,最后被剥皮.割头.津巴布韦政府正追缉那个嗜血西班牙人.据香港<明报>网站7月28日报道,受害的13岁黑 ...
  • 0x00 分析 Whatscat是一个可以上传猫咪的照片并且可以评论的php应用,地址: https://blogdata.skullsecurity.org/whatscat.tar.bz2 漏洞代码存在于login.php的密码重置模块,如下:   elseif (isset($_POST[&q ...
  • 在 ASP 中,有两个很常用的集合,一个是 Request.QueryString,另一个是 Request.Form.这两个集合可以获取 HTML 表单(HTML Forms) 提交的信息. Request.QueryString HTML 表单中的 method 有两种,一种是 get,另外一种 ...
一周排行
  • Windows 7从另一种角度上来说,包含两类大版本,一个是32位,另一个则是64位.64位系统就一定强过32位吗?你是否需要64位Windows 7?32位系统和64位系统有什么区别? 在内存与CPU上的区别 首先 ...
  • 本文介绍了在Ubuntu使用过程中遇到 is not in the sudoers file 时的解决办法. 用sudo时提示"xxx is not in the sudoers file. This in ...
  • 联想中国区消费笔记本总经理张华 易网科技讯 5月9日消息,今天"上网本 3G 家电下乡"高峰论坛在深圳开幕,包括李世鹤和李进良(博客)等3G领域专家.众多手机.PC和山寨上网本厂商的代表参加.易网 ...
  • 整理了下之前写表达验证的demo. https://github.com/namletneg/verifyForm
  • 1:a=10,b=15,在不用第三方变量的前提下,把a,b的值互换 2:已知数组int[] max={6,5,2,9,7,4,0};用快速排序算法按降序对其进行排列,并返回数组  
  • 因为TOMCAT下面的项目在访问的时候需要遵循下列格式: http: //127.0.0.080/testProject 但是实际上,我们在开发基于B/S的项目的时候,用户总是不希望见到这种必须输入项目名称的方 ...
  • IT之家讯 此前有消息称,Win10系统RTM正式版将在今年7月正式发布,而微软也一直在强调,Win7/Win8/Win8.1正版用户可以在Win10正式版发布后第一年内免费升级,此后将持续免费获得Windows10 ...
  • 一个tableView页面,的按钮用来添加行,同时可以移动行,的按钮用来删除行,不能移动行,要求第一行不能被改变(删除,移动,增加),第一行用来返回上一级. 实现效果: 上面展示了一个从根视图跳转到子视图,再从添加选 ...
  • 从飞船的残骸中出来后可以找到医疗瓶,使用医疗瓶恢复生命值,由于没有了头盔,所以艾萨克的体温下降很快,靠近沿途的火堆可以恢复体温,一旦体温降至最低,艾萨克将死亡 在克罗吉亚号飞船坠毁后,艾萨克醒来并发现自己掉在了T—沃 ...
  • 本文是作者在进行数据库功能测试时的一些心得,其中的例子是用java语言编写的,但我认为这些想法对于大多数编程环境都普遍适用.当然,我仍致力于寻找更佳的解决方案. 现实的问题是这样的:你有一个SQL数据库,一些存储过程 ...