题解 | 拓扑排序#C语言

#include<stdlib.h>

typedef struct EdgeNode{
    int adjext;
    struct EdgeNode* next;
}EdgeNode;

typedef struct VerteNode{
    int in;
    int data;
    struct VerteNode* firstEdge;
}VerteNode;

typedef struct{
    VerteNode adjList[200000];
    int numsNode,numsEdge;
}GraphAdjList;

int nums=0;

void CreateALGraph(GraphAdjList* G){
    int i,j,k;
    for(i=0;i<G->numsNode;i++){
        G->adjList[i].data=i;
        G->adjList[i].firstEdge=NULL;
        G->adjList[i].in=0;
    }
    for(k=0;k<G->numsEdge;k++){
        EdgeNode* e;
        scanf("%d",&i);
        scanf("%d",&j);
        e=(EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjext=j-1;
        e->next=G->adjList[i-1].firstEdge;
        G->adjList[i-1].firstEdge=e;
        G->adjList[j-1].in++;
    }
}

int TopologicalSort(GraphAdjList* G,int* ans){
    int i,j,gettop;
    int top=0;
    EdgeNode* e;
    int count=0;
    int* Queue=(int*)malloc(sizeof(int)*G->numsNode);
    int front=0,rear=0;
    for(int i=0;i<G->numsNode;i++){
        if(G->adjList[i].in==0)
            Queue[rear++]=i;
    }
    while(front!=rear){
        gettop=Queue[front++];
        ans[nums++]=G->adjList[gettop].data+1;
        count++;
        for(e=G->adjList[gettop].firstEdge;e;e=e->next){
            j=e->adjext;
            if(!(--G->adjList[j].in))
               Queue[rear++]=j;
        }
    }
    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* ans=(int*)malloc(sizeof(int)*G->numsNode);
    CreateALGraph(G);
    int flag=TopologicalSort(G,ans);
    if(flag==-1)
        printf("-1");
    else{
        for(int i=0;i<nums;i++){
            if(i==0)
                printf("%d",ans[i]);
            else
                printf(" %d",ans[i]);
        }
    }
    return 0;
}