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,另外一种 ...
一周排行
  •         经历了很多项目的人,就会发现编写验证代码的过程是多么极其乏味痛苦的历程,而太多的验证代码都极其相似,想尝试用个框架来解决.但在网上搜索一番,发现要么极其复杂不够灵活,要么庞大不适合我的项目.于是发挥劳 ...
  • 谷歌公司日前对外透露了一个研发全自动驾驶汽车的项目,以减少交通事故和路上通勤时间. 谷歌为这一实验动用了六台普锐斯和一台奥迪TT.这些试验车辆加装了摄影机.雷达和激光传感器,可以实现自我驾驶. 目前测试车已运行超过1 ...
  • 在看下面这篇文章之前,先介绍几个理论知识,有助于理解A*算法.   启发式搜索:启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标.这样可以省略大量无畏的搜索路径 ...
  • import org.pentaho.di.core.KettleEnvironment; import org.pentaho.di.core.database.DatabaseMeta; import org.p ...
  • 原题链接: http://oj.leetcode.com/problems/binary-tree-level-order-traversal/  这道题要求实现树的层序遍历,其实本质就是把树看成一个有向图,然后进行 ...
  • 7月30日,MSN性感相册的变异品种肆虐互联网.图/CFP 由于针对即时通讯工具MSN的病毒接连在互联网上肆虐,不堪忍受声誉损失的微软公司近日将与国内几家反病毒公司联手出击,在技术方面彻底整治针对MSN软件流行的病毒 ...
  • 就像第一章所说一样,这次学习为了快,因此说明性的文字就不想写太多了,直接帖代码吧,代码当中尽量加一些注释: 1 package a.b; 2 3 public class test 4 { 5 6 static vo ...
  • 百度云支付平台为百付宝,为了您的财产安全,请您完善个人信息,设置支付密码及安全问题 百度云支付平台为百付宝,为了您的财产安全,请您完善个人信息,设置支付密码及安全问题.具体方法如下: 1.进入百付宝首页(https: ...
  • Windows7的一个小毛病,估计有不少的朋友都遇见过,特别是在新装系统时,可能因为你安装了某个新软件或者对系统作了某此埂新,就会导致已经安装的某些软件的图标不能正常显示了.这不可不说是为Windows 7精致的小脸 ...
  • 步骤1:创建一个txt 文件touch 1.txt步骤2:使用vi 编辑文件#!/bin/sha="hello shell"echo "A is"echo $a步骤3:给文件添 ...