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,另外一种 ...
一周排行
  • 配置Tomcat[解压版] 选择解压版的Tomcat的理由是可以让我们使用多个Tomcat,但是配置上就会出现一些问题,需要我们手动进行更改配置.我的Tomcat版本是:apache-tomcat-6.0.16.zi ...
  • 易网科技讯  12月2日消息 据国外媒体报道,总部位于惠州的中国侨兴环球电话公司(Qiao Xing Universal Telephone Inc.)今日宣布称,按照与富龙投资有限公司(Dragon Fu Inve ...
  • 下载sdk版本:在hosts文件中追加以下信息: 74.125.113.121 developer.android.com 203.208.46.146 dl.google.com 203.208.46.146 dl ...
  • 从编码方面 一. 缓存 缓存是ASP.NET中提高性能的重要手段,缓存一般遵循以下原则: 1) 在页面中将静态内容与动态内容分割开来 考虑将动态内容作成用户控件 2) 缓存合理的数据 一般应当缓存应用程序集的数据.多 ...
  • fdisk查看磁盘 [[email protected] ~]# cat /etc/redhat-release Red Hat Enterprise Linux Server release 5.9 (Tikanga) [roo ...
  • SHint介绍 翻译自www.jshint.comJSHint(注意不是jslint:))是一个由javascript社区驱动开发的用于检查javascript代码错误和问题的工具,有了他,可以使你保持一个良好的编码 ...
  •  一.fork入门知识      一个进程,包括代码.数据和分配给进程的资源.fork()函数通过系统调用创建一个与原来进程几乎完全相同的进程,也就是两个进程可以做完全相同的事,但如果初始参数或者传入的变量不同,两个 ...
  • [java]   /**       * 获取所有应用       * @return 所有应用的集合       */       private List<AppInfo> queryAppInfo( ...
  • 自从win95时代以来,个人用的最长时间的输入法应该是微软的智能ABC的,但是智能ABC的记忆功能和词库实在太弱,后来开始使用微软拼音,不使用其他输入法的原因很简单,懒的装,而且你不能保证你的输入法在任何你用的机器上 ...
  • 启动mysql时出现以下错误: 解决方法: [[email protected] mysql2]# rm -rf /var/lock/subsys/mysql 再次启动mysql,一切正常了: 如果出现以下错误: 解决方 ...