拓扑排序hdu 3342 Legal or Not

发布时间:2017-3-23 14:25:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"拓扑排序hdu 3342 Legal or Not",主要涉及到拓扑排序hdu 3342 Legal or Not方面的内容,对于拓扑排序hdu 3342 Legal or Not感兴趣的同学可以参考一下。

Legal or Not Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1446    Accepted Submission(s): 603 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 这道题主要就是判断是否能拓扑排序(就是不能构成环),能的话就输出YES,不能侧输出NO。 #include <stdio.h> #include<string.h> int flag=1; int map[110][110]; void  topology(int n) { int mark[510]; memset(mark,0,sizeof(mark)); int i,j,k; for(i=0;i<n;i++) { for(j=0;j<n;j++) if(map[i][j]==1) mark[j]++; } for(i=0;i<n;i++) { j=0; while(mark[j]!=0) j++; if(j>=n)  { flag=0; break; } mark[j]=-1; for(k=0;k<n;k++) if(map[j][k]==1) mark[k]--; } if(flag==1) printf("YES\n"); else printf("NO\n"); } int main() {        int n,i,m; int start,end; while(scanf("%d%d",&n,&m)!=EOF) {  if(n==0&&m==0) break; memset(map,0,sizeof(map)); flag=1; for(i=0;i<m;i++) { scanf("%d%d",&start,&end); map[start][end]=1; }        topology(n); }  return 0; }    

上一篇:mapserver-mapfile学习4:定义符号
下一篇:拓扑排序&nbsp;hdu&nbsp;2647&nbsp;Reward

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款