#include<stdio.h>
#include<cstdlib>
#define outmax 3//最大出度
#define inmax 2//最大入度
#define vex 9//頂點(diǎn)個(gè)數(shù)
#define max 10000//定義極大值
int linjie_0[vex][outmax]={{1,2,3},{4},{4},{5},{6,7},{7},{8},{8},{-1}};//出鄰接頂點(diǎn)
int linjie_1[vex][inmax]={{-1},{0},{0},{0},{1,2},{3},{4},{4,5},{6,7}};//入鄰接頂點(diǎn)
int label_1[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓?fù)淞袠?biāo)志位，第1列是入度，第2列是出度
int labevl[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓?fù)淞袠?biāo)志位，第1列是入度（在拓?fù)渑判蜃映绦蛑兄狄淖儯?列是出度
int juzhen[vex][vex];//鄰接矩陣
int tuopu[vex],tuopu_k=0;//拓?fù)湫蛄?//int ve[vex],vl[vex];//頂點(diǎn)，事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間
//int e[vex][vex],l[vex][vex];//邊，活動(dòng)的最早開始時(shí)間和最遲開始時(shí)間，兩者相等的即為關(guān)鍵路徑
void tuopupaixu();//拓?fù)渑判蜃映绦?//void make_ve();//事件最早發(fā)生時(shí)間子程序
//void make_vl();//事件最遲發(fā)生時(shí)間子程序
//void critical_path();//關(guān)鍵路徑子程序
int main()
{
    int i,j;
    for(i=0;i<vex;i++)
    for(j=0;j<vex;j++)
	{
        tuopu[i]=0;
        //ve[i]=0;
        juzhen[i][j]=max;
        //vl[i]=max;
	}
    juzhen[0][1]=6;
    juzhen[0][2]=4;
    juzhen[0][3]=5;
    juzhen[1][4]=1;
    juzhen[2][4]=1;
    juzhen[3][5]=2;
    juzhen[4][6]=9;
    juzhen[4][7]=7;
    juzhen[5][7]=4;
    juzhen[6][8]=2;
    juzhen[7][8]=4;//初始化
    tuopupaixu();
    //make_ve();
   // make_vl();
   // critical_path();
    printf("\n");
    system("pause");
    return 0;
}


void tuopupaixu()
{
    int i,j;
    while(1)
	{
       for(i=0;i<vex;i++)
       if(labevl[i][0]==0)
       j=1;
       if(j==0)
       break;
       for(i=0;i<vex;i++)
      if(labevl[i][0]==0 && labevl[i][1]==0)
	  {
         labevl[i][0]=1;//刪除已經(jīng)排入拓?fù)湫蛄械捻旤c(diǎn)
         tuopu[tuopu_k]=i;//拓?fù)渚幪?hào)
         tuopu_k++;
         for(j=0;j<labevl[i][2];j++)
         labevl[linjie_0[i][j]][1]--;//使和排入拓?fù)湫蛄械捻旤c(diǎn)相鄰的頂點(diǎn)的入度減1
	  }
	}
    printf("拓?fù)湫蛄校?quot;);
    for(i=0;i<vex;i++)
    printf("%d",tuopu[i]);
}
/*void make_ve()
{
     printf("\n事件的最早開始時(shí)間：");
     int i,j;
     int a1,a2,a3;
     for(i=0;i<vex;i++)//按拓?fù)湫蛄械捻樞蜃?	 {
        a1=tuopu[i];
        for(j=0;j<label_1[a1][2];j++)//從源點(diǎn)到匯點(diǎn)推進(jìn)
		{
            a2=linjie_0[a1][j];//向后鄰接頂點(diǎn)
            a3=juzhen[a1][a2];//邊的權(quán)值
            if(ve[a2]<ve[a1]+a3)
            ve[a2]=ve[a1]+a3;//ve(j)=Max { ve(i)+dut(<i,j>) }
		}
	 }
     for(i=0;i<vex;i++)
     printf("[%d]-%d",i,ve[i]);
}
void make_vl()
{
     printf("\n事件的最遲開始時(shí)間：");
     int i,j;
     int a1,a2,a3;
     vl[vex-1]=ve[vex-1];//匯點(diǎn)的vl值等于其ve值
     for(i=vex-1;i>0;i--)//按逆拓?fù)湫蛄械捻樞蜃?	 {
         a1=tuopu[i];
         for(j=0;j<label_1[a1][1];j++)//從匯點(diǎn)到源點(diǎn)推進(jìn)
		 {
             a2=linjie_1[a1][j];//向前鄰接頂點(diǎn)
             a3=juzhen[a2][a1];//邊的權(quán)值
             if(vl[a2]>vl[a1]-a3)
             vl[a2]=vl[a1]-a3;//vl(i)=Min { vl(j)-dut(<i,j>) }
		 }
	 }
     for(i=0;i<vex;i++)
     printf("[%d]-%d",i,vl[i]);
}
void critical_path()
{
     printf("\n關(guān)鍵路徑：");
     int i,j;
     for(i=0;i<vex;i++)
     for(j=0;j<vex;j++)
	 {
        if(juzhen[i][j]!=max)
		{
            e[i][j]=ve[i];//e(i)=ve(i)
            l[i][j]=vl[j]-juzhen[i][j];//l(i)=vl(j)-dut(<i,j>)
            if(e[i][j]==l[i][j] && e[i][j]!=max)//關(guān)鍵路徑的判斷
            printf("[%d]-->[%d] ",i,j);
		}
	 }
}*/