题解 | #【模板】拓扑排序#

图论，有点难啊

#include <stdio.h>
#include<stdlib.h>
//邻接矩阵
/*typedef struct {
    int** edge;
    int vexnum, arcnum;
} Mgraph;

Mgraph* InitMGraph(Mgraph* gra, int maxsize, int vexnum, int arcnum) {
    gra = (Mgraph*)malloc(sizeof(Mgraph));
    gra->edge = (int**)malloc(sizeof(int*)*maxsize);
    for (int i = 0; i < maxsize; i++) {
        gra->edge[i] = (int*)malloc(sizeof(int) * maxsize);
    }
    gra->vexnum = vexnum;
    gra->arcnum = arcnum;
    for (int i = 0; i < maxsize; i++) {
        for (int j = 0; j < maxsize; j++) {
            gra->edge[i][j] = 0;
        }
    }
    return gra;
}*/
//边结点
typedef struct EdgeNode{
    int num;
    struct EdgeNode* next;
}EdgeNode;
//顶点
typedef struct vertexNode{
    int vertex;
    //入度数
    int in;
    EdgeNode* head_edge;
}vertexNode;
//邻接表
typedef struct{
    vertexNode* adjList;
    //点与边的数量
    int numsNode,numsEdge;
}GraphAdjList;

void CreateALGraph(GraphAdjList* G){
    G->adjList = (vertexNode*)malloc(sizeof(vertexNode)*G->numsNode);
    //点的初始化
    for(int i = 0;i<G->numsNode;i++){
        G->adjList[i].vertex = i;
        G->adjList[i].head_edge =  NULL;
        G->adjList[i].in = 0;
    }

    //边的初始化
    for(int i = 0;i<G->numsEdge;i++){
        int temp1,temp2;
        //从temp1->temp2
        scanf("%d %d",&temp1,&temp2);
        //申请一个边结点
        EdgeNode* edge = (EdgeNode*)malloc(sizeof(struct EdgeNode));
        //边的值为temp2-1，因为temp1和temp2为从1开始
        edge->num = temp2-1;
        edge->next = NULL;
        //temp1-1为空时
        if(G->adjList[temp1-1].head_edge == NULL)
            G->adjList[temp1-1].head_edge =edge;
        //否则头插
        else{
            EdgeNode* temp = G->adjList[temp1-1].head_edge;
            G->adjList[temp1-1].head_edge = edge;
            edge->next = temp;
        }
        //temp2入度增加
        G->adjList[temp2-1].in++;
    }
}
//拓扑
int TopologicalSort(GraphAdjList* G,int *resul){
    //申请队列
    int* Queue = (int *)malloc(sizeof(int)*G->numsNode);
    int front = 0,rear = 0;
    //结果列表的计数
    int count = 0;
    EdgeNode* e;
    //所有入度为0入队列
    for(int i = 0;i<G->numsNode;i++){
        if(G->adjList[i].in == 0) Queue[rear++] = i;
    }
    while(front != rear){
        //取一个入读为0的
        int temp = Queue[front++];
        //放置结果中
        resul[count++] = G->adjList[temp].vertex+1;
        //由于当前结点已经取走，所有以他为入度点的都--
        for(e = G->adjList[temp].head_edge;e;e = e->next){
            if(!(--G->adjList[e->num].in))
            //入读为0入队列
                Queue[rear++] = e->num;
        }
    }
    if(count == G->numsNode) return 1;
    else return -1;
}

int main() {
    GraphAdjList* G = (GraphAdjList*)malloc(sizeof(GraphAdjList));
    scanf("%d",&G->numsNode);
    scanf("%d",&G->numsEdge);
    int* resul =(int *)malloc(sizeof(int)*G->numsNode);
    CreateALGraph(G);
    int flag = TopologicalSort(G,resul);
    if(flag == -1)
        printf("-1");
    else{
        for(int i = 0;i<G->numsNode;i++){
            if(i==0) printf("%d",resul[i]);
            else printf(" %d",resul[i]);
        }
    }
    return 0;
}