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

對(duì)于是否有環(huán)，是通過(guò)一個(gè)N（節(jié)點(diǎn)數(shù)）的循環(huán)來(lái)判定。檢查并更新每個(gè)節(jié)點(diǎn)的入度數(shù)。

每找到一個(gè)入度唯一的節(jié)點(diǎn)就是它的臨邊取消，即讓他的下個(gè)節(jié)點(diǎn)的入度減一；最后看看入度為0的節(jié)點(diǎn)數(shù)是否為N。

這道題我還多加了個(gè)判斷看看是否含有多個(gè)冠軍的可能。

這道題倒是沒(méi)有那么麻煩，沒(méi)打用到拓?fù)洹?/p> 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/0803yijia/archive/2012/08/02/2620696.html

總結(jié)

以上是生活随笔為你收集整理的HDU hdu 2094 产生冠军 拓扑排序 判定环的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。