HDU1285确定比赛名次 + 拓扑排序

分类：

原题连接：?pid=1285

#include<stdio.h>#include<stdlib.h>#define Max 510typedef struct vert{int num;//结点编号struct vert* next;}G_v;typedef struct node{int InDgree,OutDgree;//出度和入度G_v* next;}G_n;G_n g[Max];void Init(){int i;for(i = 1;i < Max;i ++){g[i].InDgree = g[i].OutDgree = 0;g[i].next = NULL;}}void CreateGraph(int x,int y)//将y结点连到x节点上。{G_v* tmp = g[x].next;G_v* q = (G_v*)malloc(sizeof(G_v));q->next = NULL;q->num = y;if(tmp == NULL) g[x].next = q;else{while(tmp->next!=NULL)tmp = tmp->next;tmp->next = q;}g[x].OutDgree ++;g[y].InDgree ++;}void Top(int N){G_v *tmp;int i,count = 1;for(i = 1;i <= N;i ++){if(g[i].InDgree == 0){if(count == N)printf("%d\n",i);elseprintf("%d ",i);tmp = g[i].next;while(tmp){g[tmp->num].InDgree –;tmp = tmp->next;}i = 0;//返回重新检验所有点g[i].InDgree = –;//将已经输出的点排除count++;}}}int main(void){int N,M,x,y;Init();while(scanf("%d %d",&N,&M)!=EOF){Init();for(int i = 1;i <= M;i ++){scanf("%d %d",&x,&y);CreateGraph(x,y);}Top(N);}}

上一篇poj2367Genealogical tre

顶0踩0

，我的眼泪流了下来，浇灌了下面柔软的小草，

相关文章：

你感兴趣的文章：

标签云：