/*//////////////////////////////////////////////////////////
///////////4、實現課程的拓撲排序。(選)（加）
   問題描述：軟件專業的學生要學習一系列課程，其中有些課程必須在其先修課程完成后才能學習，具體關系見下表：
課程編號	課程名稱	先決條件
C1	程序設計基礎	無
C2	離散數學	C1
C3	數據結構	C1，C2
C4	匯編語言	C1
C5	操作系統	C3
假設每門課程的學習時間為一學期，試為該專業的學生設計教學計劃，使他們能在最短的時間內修完這些課程。
 

//////////由小謝編輯，只作學習參考，不能直接復制作為作業
///////////本人已將作品放在www.edugoo.com/guangxi/bbs上供大家學習使用
///////////////////////////////////////////////////////////*/
//拓撲排序topSort.cpp
#include<iostream.h>
//#include<iomanip.h>
#include<stdlib.h>
typedef struct
{char w1,w2;
 float w;
}RCW;
#include "graph4.h"
typedef struct
{int *data;
 int max,top;
}Stack;

void TopSort(Graph *G)
{int i,j,n,d,count=0,*D;
 Stack S;
 if(G->size==0) return;
 n=G->size;
 S.data=new int[n];
 S.max=n;S.top=-1;

 D=new int[n];
 for(j=0;j<n;j++)
  {d=0;
   for(i=0;i<n;i++)
    if(G->edge[i][j]!=0) d++;
    D[j]=d;//統計入度
    if(d==0)//入度為0
     {if(S.top==S.max-1)
       {cout<<"Stack is full!\n";exit(1);}
      S.top++;
      S.data[S.top]=j;//記錄入度為0的點
     }
  }

 while(!(S.top==-1))//如果有入度為0的點.....
 {  int w=1,ww=0;
	 if(S.top==-1)
    {cout<<"Pop an empty stack!\n";exit(1);}
     S.top--;
 i=S.data[S.top+1];


if (S.top+1==0)
{
cout<<G->data[i]<<endl;//輸出點

}
if (S.top+1!=0)
{cout<<G->data[i];//輸出點

}

  count++;//計算曾經輸出的點的個數
 for(j=0;j<n;j++)//將頂點輸出后，對頂點的入度作修改
  if(G->edge[i][j]!=0)
  {D[j]--;
   if(D[j]==0)
    {if(S.top==S.max-1)
       {cout<<"Stack is full!\n";exit(1);}
      S.top++;
      S.data[S.top]=j;//修改之后入度為0，入站記錄
 }}}//while(!(S.top==-1))
 if(count<n)
  cout<<"\nThere is a cycle.";
 free(D);
 free(S.data);
}
void main()
{cout<<"經拓撲排序后，結果為:\n";
 Graph G;int n=5,e=5;//int n=6,e=8;//n為頂點數,e為邊數
 RCW rcw[5]={{'a','b',1},{'a','c',1},{'a','d',1},{'b','c',1},
             {'c','e',1}};//1表示兩點之間有聯系
 SetGraph(&G,n);
 MakeGraph(&G,rcw,n,e);
 TopSort(&G);
 free(G.data);//釋放空間
 free(G.visited);
 for(int i=0;i<G.max;i++) free(G.edge[i]);
 free(G.edge);
 cin.get();//等待函數（可以去掉哦）
}