這一道題的話 ?數(shù)據(jù)有一點(diǎn)問題 ? ?........ ? ? 例如 不過 還是 ? 能理解一下 ?試試吧 ?.........

3 5 A<B B<C C<A A<C B<A 這幾組數(shù)據(jù) 明顯反映出來 這是成環(huán)的 , 然后 按照 輸入輸出案例來說 這個(gè)是 有序的 ABC

　?

? ? ?

題目要求 ? ? 在每組數(shù)據(jù)的 ? 第一行 ?給你需要排序 的 字母數(shù) ? ?和 ?他們之間的關(guān)系數(shù)量 ? ? ?然后 ?輸入每組數(shù)據(jù) ? ?你首先許亞萍判斷在輸入 ?第幾組 數(shù)據(jù)的時(shí)候 出現(xiàn)了 環(huán) ? ? 其次判斷 ? ?到第幾組關(guān)系的時(shí)候 ? 可以確定唯一的序列 ?如果上面兩個(gè) 都不行的話 ? ?就輸出 ? 第三種情況 ?不能確定 ?唯一 的 ? 排序序列

內(nèi)存越界.....醉了 . 明天看 ?睡覺覺?

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack> 10 #include<string> 11 #include<sstream> 12 #include<map> 13 #include<cctype> 14 using namespace std; 15 int n,m,a[30][30],visited[30],flag,fuck,mark,result[30],temp[30],count1,flag1; 16 void topsort(int q) 17 { 18 fuck=0; 19 for(int j=0;j<n;j++) 20 temp[j]=visited[j]; // 21 count1=0; 22 for(int i=1;i<=n;i++) // 其實(shí)只是普通的 拓?fù)渑判? 重復(fù)化了一下而已 ... 23 { 24 fuck=mark=0; 25 for(int j=0;j<n;j++) 26 { 27 if(temp[j]==0) 28 { 29 flag=j; 30 mark++; 31 } 32 } 33 if(mark==0) 34 { 35 printf("Inconsistency found after %d relations.\n",q+1); 36 flag1=fuck=1; 37 break; 38 } 39 temp[flag]--; // 找到了 flag 他沒有兒子 / 現(xiàn)在 將他標(biāo)記為 -1; 40 if(mark==1) 41 { 42 result[i]=flag; // 將 該點(diǎn)儲(chǔ)存起來 43 count1++; 44 } 45 for(int j=0;j<n;j++) // 將 flag的 所有爸爸的 兒子數(shù) -1 46 { 47 if(a[flag][j]) 48 { 49 temp[j]--; 50 } 51 } 52 } 53 } 54 int main() 55 { 56 while(scanf("%d%d",&n,&m),(n||m)) 57 { 58 flag1=fuck=count1=mark=flag=0; 59 memset(visited,0,sizeof(visited)); 60 memset(a,0,sizeof(a)); 61 for(int i=0;i<m;i++) 62 { 63 char d,c,b; 64 scanf(" %c%c%c",&b,&d,&c); 65 if(flag1) 66 continue; 67 a[b-'A'][c-'A']=1; // c 有一個(gè)叫做b 的兒子 68 visited[c-'A']++; // c 的 兒子 數(shù)量 ++ 69 topsort(i); // 第一次進(jìn)去的時(shí)候 就相當(dāng)于 只有一組的關(guān)系 70 if(fuck) 71 ; 72 else 73 { 74 if(count1==n) 75 { 76 printf("Sorted sequence determined after %d relations: ",i+1); 77 for(int i=1;i<=n;i++) 78 printf("%c",result[i]+'A'); 79 printf(".\n"); 80 flag1=1; 81 } 82 } 83 if(!flag1&&i==m-1) 84 { 85 printf("Sorted sequence cannot be determined.\n"); 86 flag1=1; 87 } 88 } 89 } 90 return 0; 91 }

?

?

?

?

1 #include<stdio.h> 2 #include<string.h> 3 int map[27][27],indegree[27],q[27]; 4 int TopoSort(int n) //拓?fù)渑判?/span> 5 { 6 int c=0,temp[27],loc,m,flag=1,i,j; ////flag=1:有序 flag=-1:不確定 7 for(i=1;i<=n;i++) 8 temp[i]=indegree[i]; 9 for(i=1;i<=n;i++) 10 { 11 m=0; 12 for(j=1;j<=n;j++) 13 if(temp[j]==0) { m++; loc=j; } //查找入度為零的頂點(diǎn)個(gè)數(shù) 14 if(m==0) return 0; //有環(huán) 15 if(m>1) flag=-1; // 無序 16 q[c++]=loc; //入度為零的點(diǎn)入隊(duì) 17 temp[loc]=-1; 18 for(j=1;j<=n;j++) 19 if(map[loc][j]==1) temp[j]--; 20 } 21 return flag; 22 } 23 24 int main() 25 { 26 int m,n,i,sign; //當(dāng)sign=1時(shí)，已得出結(jié)果 27 char str[5]; 28 while(scanf("%d%d",&n,&m)) 29 { 30 if(m==0&&n==0) break; 31 memset(map,0,sizeof(map)); 32 memset(indegree,0,sizeof(indegree)); 33 sign=0; 34 for(i=1;i<=m;i++) 35 { 36 scanf("%s",str); 37 if(sign) continue; //一旦得出結(jié)果，對(duì)后續(xù)的輸入不做處理 38 int x=str[0]-'A'+1; 39 int y=str[2]-'A'+1; 40 map[x][y]=1; 41 indegree[y]++; 42 int s=TopoSort(n); 43 if(s==0) //有環(huán) 44 { 45 printf("Inconsistency found after %d relations.\n",i); 46 sign=1; 47 } 48 if(s==1) //有序 49 { 50 printf("Sorted sequence determined after %d relations: ",i); 51 for(int j=0;j<n;j++) 52 printf("%c",q[j]+'A'-1); 53 printf(".\n"); 54 sign=1; 55 } 56 } 57 if(!sign) //不確定 58 printf("Sorted sequence cannot be determined.\n"); 59 } 60 return 0; 61 }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/A-FM/p/5369854.html

總結(jié)

以上是生活随笔為你收集整理的Sorting It All Out 拓扑排序+确定点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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