include<stdio.h>

include<malloc.h>

define MAX_VERTEX_NUM 20

define TRUE 1

define FALSE 0

/图的邻接表表示法/
typedef char VertexData;
//弧结点结构
typedef struct ArcNode {
int adjvex; //该弧指向顶点的位置
struct ArcNode* nextarc; //指向下一条弧的指针
}ArcNode;
//表头结点结构
typedef struct VertexNode {
VertexData data; //顶点数据
ArcNode* firstarc; //指向该顶点的第一条弧的指针
}VertexNode;
//邻接表结构
typedef struct {
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum, arcnum; //图的顶点数和弧数
}AdjList;

/求顶点位置/
char LocateVertex(AdjList* G, VertexData v) {
int k;
for (k = 0; k < G->vexnum; k++) {
if (G->vertex[k].data == v)
break;
}
return k;
}

/创建有向图的邻接表/
char CreateAdjList(AdjList* G) {
int i, j, k;
VertexData v1, v2;
ArcNode* p;
printf("输入图的顶点数和弧数："); //输入图的顶点数和弧数
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("输入图的顶点：");
for (i = 0; i < G->vexnum; i++) { //输入图的顶点，初始化顶点结点
scanf(" %s", &(G->vertex[i].data));
G->vertex[i].firstarc = NULL;
}
for (k = 0; k < G->arcnum; k++) {
printf("输入第%d条弧的两个顶点：", k + 1);
scanf(" %s %s", &v1, &v2); //输入一条弧的两个顶点
i = LocateVertex(G, v1);
j = LocateVertex(G, v2);
p = (ArcNode*)malloc(sizeof(ArcNode)); //申请新弧结点
p->adjvex = j;
p->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = p;
}
}

/顺序栈的存储结构，辅助栈/
typedef struct {
int elem[MAX_VERTEX_NUM]; //用于存放栈中元素的一维数组
int top; //存放栈顶元素的下标，top为-1表示空栈
}SeqStack;

/初始化顺序栈/
void InitStack(SeqStack* S) {
S->top = -1;
}

/判空/
int IsEmpty(SeqStack* S) {
if (S->top == -1) //栈为空
return TRUE;
else
return FALSE;
}

/顺序栈进栈/
int Push(SeqStack* S, int x) {
if (S->top == MAX_VERTEX_NUM - 1) //栈已满
return FALSE;
S->top++;
S->elem[S->top] = x; //x进栈
return TRUE;
}

/顺序栈出栈/
int Pop(SeqStack* S) {
if (S->top == -1) //栈为空
return FALSE;
S->top--;
return TRUE;
}

int indegree[MAX_VERTEX_NUM]; //存放各顶点入度

/求各顶点入度算法/
void FindID(AdjList G) {
int i;
ArcNode* p;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for (i = 0; i < G.vexnum; i++) {
p = G.vertex[i].firstarc;
while (p != NULL) {
indegree[p->adjvex]++;
p = p->nextarc;
}
}
}

/拓扑排序算法/
int TopoSort(AdjList G) {
int i, count = 0, k;
SeqStack S;
ArcNode* p;
FindID(G); //求各顶点入度
InitStack(&S); //初始化辅助栈
for (i = 0; i < G.vexnum; i++) {
if (indegree[i] == 0)
Push(&S, i); //将入度为0的顶点入栈
}
while (!IsEmpty(&S)) {
i = S.elem[S.top];
Pop(&S);
printf("%c ", G.vertex[i]);
count++;
p = G.vertex[i].firstarc;
while (p != NULL) {
k = p->adjvex;
indegree[k]--; //i号顶点的每个邻接点的入度减1
if (indegree[k] == 0)
Push(&S, k); //若入度减为0则入栈
p = p->nextarc;
}
}
if (count < G.vexnum) {
printf("该图存在回路！\n");
return FALSE;
}
else
return TRUE;
}

void main() {
AdjList G;
CreateAdjList(&G);
printf("\n拓扑排序：");
TopoSort(G);
//return 0;
}