由于采用不同方式实现的拓扑排序，输出序列不惟一，因此对此题进行修订。不再检查拓扑序列是否一致。 【问题描述】 设一有向图（如下所示），求图的邻接表表示，用拓扑序列检测有向图是否存在环。 image.png 【输入形式】 输入顶点信息，以#结束； 输入弧的信息，以-1，-1结束。 【输出形式】 输出邻接表形式 输出拓扑排序的顶点数 输出是否存在环 【样例输入1】 ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1 【样例输出1】 A,0:->1 B,2:->2 C,1:->3 D,1: E,0:->5->1 F,1: 6 no ring 【样例输入2】 ABCDEF# 1,0 1,3 2,1 2,5 3,2 3,4 3,5 4,0 5,0 5,1 5,4 -1,-1 【样例输出2】 A,3: B,2:->3->0 C,1:->5->1 D,1:->5->4->2 E,2:->0 F,2:->4->1->0 0 has ring 【样例说明】 样例2中，有向图拓扑序列一个顶点都无法输出。 【评分标准】 给出c语言代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100
#define OK 1
#define ERROR 0

typedef char VertexType;
typedef int Status;

typedef struct ArcNode {
    int adjvex; // 邻接点在数组中的位置
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    VertexType data; // 顶点信息
    int indegree; // 入度
    ArcNode *firstarc; // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 图的顶点数组
    int vexnum, arcnum; // 顶点和弧数目
} ALGraph;

Status CreateGraph(ALGraph *G) {
    scanf("%c", &G->vertices[0].data);
    G->vexnum = 1;
    while (getchar() != '#') {
        scanf("%c", &G->vertices[G->vexnum].data);
        ++G->vexnum;
    }
    getchar(); // 读取回车
    for (int i = 0; i < G->vexnum; ++i) {
        G->vertices[i].firstarc = NULL;
        G->vertices[i].indegree = 0;
    }
    int v1, v2;
    while (1) {
        scanf("%d,%d", &v1, &v2);
        if (v1 == -1 && v2 == -1) break;
        ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode));
        arc->adjvex = v2;
        arc->nextarc = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = arc;
        ++G->arcnum;
        ++G->vertices[v2].indegree;
    }
    return OK;
}

Status TopologicalSort(ALGraph G) {
    int count = 0;
    int *stack = (int *) malloc(G.vexnum * sizeof(int));
    int top = -1;
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.vertices[i].indegree == 0) {
            stack[++top] = i;
        }
    }
    while (top != -1) {
        int v = stack[top--];
        printf("%c ", G.vertices[v].data);
        ++count;
        for (ArcNode *arc = G.vertices[v].firstarc; arc != NULL; arc = arc->nextarc) {
            int w = arc->adjvex;
            if (--G.vertices[w].indegree == 0) {
                stack[++top] = w;
            }
        }
    }
    free(stack);
    if (count != G.vexnum) {
        return ERROR;
    } else {
        return OK;
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    if (TopologicalSort(G) == OK) {
        printf("\nno ring");
    } else {
        printf("\nhas ring");
    }
    return 0;
}