#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 510
int N, M;
int mp[LEN][LEN];
int indgr[LEN];
int s[LEN];
int list[LEN];
int lstlen;
int findZeroIndgr()
{
int i;
for(i = 0; i < N; i++)
if(s[i] == 0 && indgr[i] == 0)
return i;
}
void Topological()
{
int i, j;
int zr;
for(i = 0; i < N; i++)
{
zr = findZeroIndgr();
s[zr] = 1;
list[lstlen++] = zr;
for(j = 0; j < N; j++)
if(mp[zr][j] == 1)
indgr[j]--;
}
}
int main()
{
int i, j;
int p1, p2;
while(scanf("%d%d", &N, &M) != EOF)
{
memset(mp, 0, sizeof(mp));
memset(indgr, 0, sizeof(indgr));
memset(s, 0, sizeof(s));
for(i = 0; i < M; i++)
{
scanf("%d%d", &p1, &p2);
p1--;
p2--;
if(mp[p1][p2] == 0)
{
mp[p1][p2] = 1;
indgr[p2]++;
}
}
lstlen = 0;
Topological();
int gard = 0;
for(i = 0; i < lstlen; i++)
if(gard++ != 0)
printf(" %d", list[i] + 1);
else
printf("%d", list[i] + 1);
putchar(10);
}
//system("pause");
}
posted on 2012-08-18 17:17
小鼠標 閱讀(243)
評論(0) 編輯 收藏 引用 所屬分類:
圖論