#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
#include <iostream.h>

typedef struct ArcCell{
	int adj;/*頂點關系類型，用1表示相鄰，0表示不相鄰*/
}ArcCell,**AdjMatrix;/*鄰接矩陣*/

typedef struct type{ 
	char data[3];/*頂點值*/
	int info;/*弧的長度*/
	struct type *next;/*頂點的下一個指針*/
}VertexType;

typedef struct{
	VertexType *vexs;/*頂點向量*/
	AdjMatrix arcs;/*鄰接矩陣*/
	int vexnum,arcnum;/*圖的頂點數和邊數*/
}MGraph;

/* ****************** */
typedef int Status;
#define STACK_INIT_SIZE 50
typedef int ElemType;
typedef struct STACK /*定義棧類型*/
{
  ElemType *base;
  ElemType *top;
  int stacksize;
  int length;
}SqStack,*Stack;

void InitStack(Stack *S) /*初始化棧*/
{
  *S=(SqStack *)malloc(sizeof(SqStack));
  (*S)->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
  if(!(*S)->base)exit(-1);
  (*S)->top=(*S)->base;
  (*S)->stacksize=STACK_INIT_SIZE;
  (*S)->length=0;
}


Status DestroyStack(Stack *S) /* 銷毀棧*/
{
	free((*S)->base);
	free((*S));
	return 1;
}

Status StackEmpty(SqStack S) /*判斷棧空否*/
{
	if(S.top==S.base)
		return 1;
	else
		return 0;
}
void Push(Stack *S,ElemType e)  /*把數據壓入棧*/
{
  if((*S)->top - (*S)->base>=(*S)->stacksize)
   {
	  (*S)->base=(ElemType *) realloc((*S)->base,
     ((*S)->stacksize + 10) * sizeof(ElemType));
	  if(!(*S)->base)
		  exit(-1);
     (*S)->top=(*S)->base+(*S)->stacksize;
     (*S)->stacksize +=10;
   }
  *((*S)->top++)=e;
  ++(*S)->length;
}

Status Pop(Stack *S,ElemType *e)/*刪除棧頂元素*/
{
  if((*S)->top==(*S)->base) return 0;
  *e=*((*S)->top-1);
  --(*S)->length;
  (*S)->top--;
  return 1;
}


/* ******************** */
void InitGraph(MGraph *G)/*初始圖*/
{ 
	int i,nu,mu;
	printf("\n輸入頂點的個數和（邊）弧的個數：");
	scanf("%d%d",&nu,&mu);
	G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
	for(i=0;i<nu;i++)/*分配鄰接矩陣空間*/
		G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
	G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配頂點空間*/
	G->vexnum=nu;G->arcnum=mu;/*圖的頂點數和邊數*/
}


void DestroyGraph(MGraph *G)/* 銷毀圖*/
{
	int i;
	free(G->vexs);
	for(i=0;i<G->vexnum;i++)
		free(G->arcs[i]);
}

void InsertGraph(MGraph *G,int i,VertexType e)
{ 
	if(i<0||i>G->vexnum)
		return;
	G->vexs[i].next=e.next;
	G->vexs[i].info=e.info;
	strcpy(G->vexs[i].data,e.data);
}

int Locate(MGraph G,VertexType v1)/*確定v1在圖頂點中的位置*/
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(strcmp(v1.data,G.vexs[i].data)==0)
			return i;
		return -1;
}


void CreateUND(MGraph *G)/*采用數組（鄰接矩陣）和鄰接表表示無向圖*/
{
	int i,j,k,*p,d,w;
	VertexType v1,v2,*q2,*q;
	p=(int *)malloc(G->vexnum*sizeof(int)); 
	for(i=0;i<G->vexnum;i++) 
		p[i]=0;
	for(i=0;i<G->vexnum;++i)/*初始鄰接表*/
	{ 
		for(j=0;j<G->vexnum;++j)
			G->arcs[i][j].adj=0;
	}
	printf("\n");
	printf("按順序輸入頂點(方向)和它們的間長度再頂點：如 'v1 3 v2' : \n");
	for(k=0;k<G->arcnum;++k)
	{
		printf("輸入第 %d 條弧: \n",k+1);
		d=0;
		scanf("%s%d%s",v1.data,&w,v2.data);/*輸入相鄰的兩個點值*/
		i=Locate(*G,v1);j=Locate(*G,v2);/*用i 和j來確定它們的位置*/
		G->arcs[i][j].adj=1;
		q2=(VertexType *)malloc(sizeof(VertexType));/*分配一個空間*/
		strcpy(q2->data,G->vexs[j].data);q2->info=w;
		q2->next=NULL;
		if(p[i]==0) 
		{
			G->vexs[i].next=q2;p[i]++;
		}
		else 
		{
			q=&(G->vexs[i]);
			while(d!=p[i])
			{
				d++;q=q->next;
			}
			p[i]++;
			q->next=q2;/*接在最后*/
		}   
	}
 free(p);
}


void FindInDegree(MGraph G,int *indegree)/*對各頂點求入度，鄰接矩陣的列*/
{
	int i,j;
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			if(G.arcs[j][i].adj==1)
				indegree[i]++;
}


int *ve,*vl;/*最早發生時間和最遲發生時間數組，全局的*/
int TopologicalOrder(MGraph G,Stack *T)/*有向圖采用鄰接表存儲結構，
									   歡迎光臨學網,收藏本篇文章 [1] [2] [3] [4]無回路返回1*/
{
	Stack S;
	int i,k,count,*indegree;
	VertexType *p;
	indegree=(int *)malloc(G.vexnum*sizeof(int));/*度數組空間*/
	ve=(int *)malloc(G.vexnum*sizeof(int));/*最早發生時間的數組空間*/
	for(i=0;i<G.vexnum;i++)
		indegree[i]=0;/*初始化*/
	for(i=0;i<G.vexnum;i++)
		ve[i]=0;/*初始化*/
	FindInDegree(G,indegree);/*求各點入度*/
	InitStack(&S);/*初始化棧*/
	InitStack(T);
	for(i=0;i<G.vexnum;++i)
		if(!indegree[i]) 
			Push(&S,i);/*入度為0進棧*/
		count=0;/*對輸出頂點計數*/
		while(!StackEmpty(*S))
		{
			Pop(&S,&i);/*拿出入度為0 的*/
			Push(T,i);/*i號頂點入T棧*/
			++count;/*計數*/
			p=G.vexs[i].next;
			while(p)
			{
				k=Locate(G,*p);
				if(!(--indegree[k])) Push(&S,k);/*減一后為0就入棧*/
				if(ve[i]+p->info>ve[k]) ve[k]=ve[i]+p->info;/*在它的所有鄰點中找出能使最大*/
				p=p->next;
			}
		}
		DestroyStack(&S);
		free(indegree);
		if(count<G.vexnum)
			return 0;/*有向圖有回路*/
		else 
			return 1;
}


int CriticalPath(MGraph G)/*G為有向網，輸出G的各項關鍵活動*/
{
	Stack T;
	int j,k,dut,e1,e2;
	char tag;
	VertexType *p;
	if(!TopologicalOrder(G,&T))
		return 0;/*有回路就不做*/
	vl=(int *)malloc(G.vexnum*sizeof(int));/*最遲發生時間數組空間*/
	for(j=0;j<G.vexnum;j++)/*初始化事件的最遲發生時間*/
		vl[j]=ve[j];
	while(!StackEmpty(*T))/*按拓撲逆序求各事件的 vl 值*/
	{ 
		Pop(&T,&j);/*從最后一個開始*/
		p=G.vexs[j].next;
		while(p)
		{
			k=Locate(G,*p);/*鄰點的位置*/
			dut=p->info;/*兩點間的長度*/
			if(vl[k]-dut>vl[j]) 
				vl[j]=vl[k]-dut;
			p=p->next;
		}
	}
	for(j=0;j<G.vexnum;j++)
		printf("事件 %s 的最早和最遲發生時間分別為 *%d* 和 *%d*\n",G.vexs[j].data,ve[j],vl[j]);
	printf("關鍵活動為：\n");
	for(j=0;j<G.vexnum;j++)/*求關鍵活動和它的值，頂點是事件，弧是活動*/
	{
		p=G.vexs[j].next;/*每個事件要依賴它的鄰點才可知是否最早=最遲*/
		while(p)
		{
			k=Locate(G,*p);/*鄰點的位置*/
			dut=p->info;/*弧長*/
			e1=ve[j];e2=vl[k]-dut;/*如果最早開始時間=最遲開始時間，最遲為鄰點減去弧長*/
			if(e1==e2) 
				tag='*';
			else 
				tag=' ';
			if(tag=='*')
				printf("*%s* 到 *%s* 長度為*%d* 發生時間為 *%d*\n",G.vexs[j].data,G.vexs[k].data,dut,e2); 
			p=p->next;
		}
	}
	free(vl);free(ve);DestroyStack(&T);
	return 1;
}


void main()
{
	MGraph G;
	VertexType e,*p;
	int i;
	InitGraph(&G);
	printf("頂點值： \n");
	for(i=0;i<G.vexnum;++i)/*給圖頂點向量付值*/
	{
		scanf("%s",e.data);
		e.next=NULL;
		e.info=9999;
		InsertGraph(&G,i,e);
	}
	CreateUND(&G);/*構造圖結構*/
	printf("鄰接表為：\n");
	for(i=0;i<G.vexnum;i++)/*輸出鄰接表*/
	{
		printf(" *%s* ",G.vexs[i].data);
		p=G.vexs[i].next;
		while(p)
		{
			printf(" *%s* ",p->data);
			p=p->next;
		}
		printf("\n");
	}
	getch();/*暫停*/
	CriticalPath(G);/*關鍵活動函數*/
	DestroyGraph(&G);/*銷毀圖*/
	getch();
}