[cpp] /* AOV網絡及拓撲排序 1、在有向無環圖中，用頂點表示活動，用有向邊<u，v>表示活動u必須先與活動v,這種有向圖叫AOV網絡。 2、若<u，v>，則u是v的直接前驅，v是u的直接後繼；若<u，u1，u2，···un，v>則稱u是v的前驅，v是u的後繼。 www.2cto.com 3、前驅後繼關系有傳遞性和反自反性。則可以推斷AOV網絡必須是有向無環圖。 4、拓撲排序實現方法： 1）從AOV網絡中選擇一個入度為0的頂點並輸出； 2）從AOV網絡中刪除該頂點以及該頂點發出的所有邊； 3）重復1）和2），直到找不到入度為0的頂點； 4）如果所有頂點都輸出了則拓撲排序完成，否則說明此圖是有環圖。 輸入描述：首先是頂點個數n和邊數m；然後m行是每條有向邊的起始點u，v； 頂點序號從1開始，輸入文件最後一行為0 0 表示結束。 輸入樣例： 樣例輸出： 6 8 5 1 4 3 2 6 1 2 Network has a cycle! 1 4 2 6 3 2 3 6 5 1 5 2 5 6 6 8 1 3 1 2 2 5 3 4 4 2 4 6 5 4 5 6 0 0 */ #include<stdio.h> #include<string.h> #define MAXN 10 struct Arcnode { int to; struct Arcnode *next; }; Arcnode* List[MAXN]; int n,m,count[MAXN]; char output[100]; void topsort() { int i,top=-1; Arcnode* temp; bool bcycle=false; int pos=0; for(i=0; i<n; i++) if(count[i]==0) { count[i]=top; top=i; } for(i=0; i<n; i++) { if(top==-1) { bcycle=true; break; } else { int j=top; top=count[top]; pos+=sprintf(output+pos,"%d ",j+1); temp=List[j]; while(temp!=NULL) { int k=temp->to; if(--count[k]==0) { count[k]=top; top=k; } temp=temp->next; } } } if(bcycle) printf("Network has a cycle!\n"); else { int len=strlen(output); output[len-1]=0; printf("%s\n",output); } } int main() { int i,v,u; //freopen("input.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { www.2cto.com if(n==0 && m==0) break; memset(List,0,sizeof(List)); memset(count,0,sizeof(count)); memset(output,0,sizeof(output)); Arcnode* temp; for(i=0;i<m;i++) { scanf("%d%d",&u,&v); u--; v--; count[v]++; temp=new Arcnode; temp->to=v; temp->next=NULL; if(List[u]==NULL) List[u]=temp; else { temp->next=List[u]; List[u]=temp; } } topsort(); for(i=0;i<n;i++) { temp=List[i]; while(temp!=NULL) { List[i]=temp->next; delete temp; temp=List[i]; } } } return 0; }
