HDU hdu 2094 产生冠军 拓扑排序 判定环

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=2094

对于是否有环，是通过一个N（节点数）的循环来判定。检查并更新每个节点的入度数。

每找到一个入度唯一的节点就是它的临边取消，即让他的下个节点的入度减一；最后看看入度为0的节点数是否为N。

这道题我还多加了个判断看看是否含有多个冠军的可能。

这道题倒是没有那么麻烦，没打用到拓扑。

View Code 1 #include <stdio.h> 2 #include <string.h> 3 struct node 4 { 5 char str[1005]; 6 }a[1005]; 7 8 int count; 9 int map[1005][1005]; 10 int in[1005]; 11 int main() 12 { 13 int c,b,n,i,j,leap,flag; 14 char s1[105],s2[105]; 15 while(scanf("%d",&n)&&n) 16 { 17 count = -1; 18 memset(in,0,sizeof(in)); 19 for(i = 0;i < n;i++) 20 { 21 scanf("%s %s",s1,s2); 22 leap = 0; 23 for(j = 0;j <= count;j++) 24 if(strcmp(s1,a[j].str) == 0) 25 { 26 leap = 1; 27 break; 28 } 29 if(!leap) 30 count++,strcpy(a[count].str,s1); 31 c = j; 32 flag = 0; 33 for(j = 0;j <= count;j ++) 34 if(strcmp(s2,a[j].str) == 0) 35 { 36 flag = 1; 37 break; 38 } 39 if(!flag) 40 count++,strcpy(a[count].str,s2); 41 b = j; 42 map[c][b] = 1; 43 in[b]++; 44 } 45 leap = 0; 46 for(i = 0;i <= count;i++) 47 if(in[i] == 0) 48 leap++; 49 if(leap > 1||leap == 0) 50 puts("No"); 51 else 52 printf("Yes\n"); 53 } 54 return 0; 55 }

 

转载于:https://www.cnblogs.com/0803yijia/archive/2012/08/02/2620696.html

总结

以上是生活随笔为你收集整理的HDU hdu 2094 产生冠军 拓扑排序 判定环的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。