拓扑

#include <stdio.h>
#include <malloc.h>
#define N 20

//图的邻接表-边或弧存储
typedef struct EdgeNode {
	int adjvex;
	struct EdgeNode *next;
} EdgeNode;

//图的邻接表-顶点存储（增加了入度域）
typedef struct VNode {
	char data;
	int ind;  //顶点入度
	struct EdgeNode *link;
} VNode;

//图的邻接表表示
typedef struct ALgraph {
	int vexnum, arcnum;
	VNode *adjlist[N];
} ALGraph;

void createGraph_list(ALGraph *g);
int topSort(ALGraph *g);

//读入数据创建带入度的邻接表
void createGraph_list(ALGraph *g) {
	char v;
	int i = 0, j;
	EdgeNode *add, *temp;
	v = getchar();
	while (v != '#') {
		g->adjlist[i] = (VNode *)malloc(sizeof(VNode));
		g->adjlist[i] ->data = v;
		g->adjlist[i]->link = NULL;
		g->adjlist[i]->ind = 0;
		i++;
		v = getchar();
	}
	getchar();
	g->vexnum = i;
	g->arcnum = 0;
	scanf("%d,%d", &i, &j);
	while (i != -1 && j != -1) {
		add = (EdgeNode *)malloc(sizeof(EdgeNode));
		add->adjvex = j;
		add->next = g->adjlist[i]->link; // 将边节点添加到链表头部
		g->adjlist[i]->link = add;
		g->adjlist[j]->ind++;
		g->arcnum++;
		scanf("%d,%d", &i, &j);
	}




}

//拓扑排序，判断图中是否存在环，存在返回0
int topSort(ALGraph *g) {
	int Stack[N];
	int top = -1;
	int visit[N] = { 0 };
	int count = 0;
	EdgeNode *p;
	for (int i = 0; i < g->vexnum; i++) {
		if (g->adjlist[i]->ind == 0) {
			Stack[++top] = i;
			visit[i] = 1;
		}
	}
	while (top != -1) {
		int oldvex = Stack[top--];
		count++;
		for (p = g->adjlist[oldvex]->link; p; p = p->next) {
			if (--g->adjlist[p->adjvex]->ind == 0) {
				if (!visit[p->adjvex]) {
					Stack[++top] = p->adjvex;
					visit[p->adjvex] = 1;
				}
			}
		}
	}
	if (count == g->vexnum) {
		return 1;
	} else {
		return 0;
	}
}


int main() {
	ALGraph g;
	int i;
	EdgeNode *s;
	createGraph_list(&g);
	for (i = 0; i < g.vexnum; i++) {
		printf("%c,%d:", g.adjlist[i]->data, g.adjlist[i]->ind);
		s = g.adjlist[i]->link;
		while (s != NULL) {
			printf("->%d", s->adjvex);
			s = s->next;
		}
		printf("\n");
	}
	i = topSort(&g);
	if (i == 1) {
		printf("%d\n", g.vexnum);
		printf("no ring\n");
	} else {
		printf("%d\n", i);
		printf("has ring\n");
	}
	return 0;
}