#include<stdio.h> #define MAX_VERTEX_NUM 60 #define TRUE 1 #define FALSE 0 typedef int AdjType; typedef int Type; typedef struct { int num; AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; }MGraph; void Push(int S[],int *n,int e) { S[(*n)++]=e; } Type Pop(int S[],int *n) { int e=S[--(*n)]; return e; } Type Empty(int S[],int *n) { if(!*n) return TRUE; else return FALSE; } void TopologicalSort(MGraph *G) { char indegree[MAX_VERTEX_NUM]={0}; int order[MAX_VERTEX_NUM]={0}; int k=0,count=0,n=0; int S[G->num]; for(int i=0;i<G->num;i++) { S[i]=-1; } for(int j=0;j<G->num;j++) { for(int i=0;i<G->num;i++) indegree[j]=indegree[j]+G->A[i][j]; if(!(indegree[j])) Push(S,&n,j); } while(!(Empty(S,&n))) { int top=Pop(S,&n); order[k++]=top; count++; for(int i=0;i<G->num;i++) { if((indegree[i]==1)&&(G->A[top][i]==1)) Push(S,&n,i); indegree[i]=indegree[i]-G->A[top][i]; } } if(count<G->num) { printf("ERROR\n"); } else { for(int i=0;i<k;i++) printf("%d ",order[i]); printf("\n"); } } int main() { MGraph G; int N; scanf("%d",&N); G.num=N; AdjType a[N][N]; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { scanf("%d",&a[i][j]); } } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { G.A[i][j]=a[i][j]; } } TopologicalSort(&G); return 0; } /************************************************************** Problem: 2164 User: admin Language: C Result: Accepted Time:12 ms Memory:1144 kb ****************************************************************/