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,另外一种 ...
一周排行
  • 题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1].问安排怎样的合并顺序,能够使得总合并代价达到 ...
  • 很多人都说Windows 7只是基于Vista的改进,其实Windows 7还有很多自己独创之处,比如"库"功能,更方便的AERO特效等等.不过大部分人都认为,改进之后的任务栏才是Windows ...
  • admin:Administrators权限   bz_canusewhineatothers:可定期向其它用户发送有关bug的邮件   bz_canusewhines: 用户在这个组,才能向其发送上面的whinin ...
  • 5月19日消息,云计算或将成为促进变革的重要力量,但<华尔街日报>网站一篇题为<忘记“云”;“雾”才是科技的未来>的文章却指出,由于接入设备激增,网络带宽有限,“雾计算”或许才会带来真正的计算 ...
  •                 本场演讲嘉宾是淘米集团手套游戏副总裁许哲鹰 许哲鹰:我要跟大家分享的是关于这款游戏上线以后总结的经验.这款游戏是通过触控在几个渠道刚刚开始的内部测试,还不算 "" ...
  • TortoiseSVN 是 Subversion 版本控制系统的一个免费开源客户端,可以超越时间的管理文件和目录.文件保存在中央版本库,除了能记住文件和目录的每次修改以外,版本库非常像普通的文件服务器.你可以将文件恢 ...
  • Android开发中的布局很重要吗?那是当然.一切的显示样式都是由这个布局决定的,你说能不重要吗.要实现一个好的布局,不只是实现了.显示出来就完了,不管层次,堆砌代码也可以实现功能,但是这显然违背了Android布局 ...
  • [Redis关键点系列+1]http://blog.csdn.net/jsjwk/article/category/1232685[renfufei的专栏]Redis: http://blog.csdn.net/re ...
  •   由于ejs的升级,<node.js开发指南>中使用的  partial 函数已经摒弃,使用foreach,include代替   原来的代码是: <%- partial('listitem',i ...
  • 最近工作有所变动.公司需要建设企业信息化,而我就是执行者.但是,这个任务就像<把信送给加西亚>,老板在给任务的时候,并没有告诉我具体的要求.而且老板非常直白地告诉我,他也不知道到底要作成什么样子的.所幸的 ...