int c[105], g[105][105], n, t;
int topo[105];
bool dfs(int u)
{
c[u] = -1;
for (int v = 1; v <= n; v++) if (g[u][v])
{
if (c[v] < 0) return false;
else if (!c[v] && !dfs(v)) return false;
}
c[u] = 1; topo[--t] = u;
return true;
}
bool toposort()
{
t = n;
mem(c, 0);
for (int i = 1; i <= n; i++) if (!c[i])
if (!dfs(i)) return false;
return true;
}#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int c[105], g[105][105], n, t;
int topo[105];
bool dfs(int u)
{
c[u] = -1;
for (int v = 1; v <= n; v++) if (g[u][v])
{
if (c[v] < 0) return false;
else if (!c[v] && !dfs(v)) return false;
}
c[u] = 1; topo[--t] = u;
return true;
}
bool toposort()
{
t = n;
mem(c, 0);
for (int i = 1; i <= n; i++) if (!c[i])
if (!dfs(i)) return false;
return true;
}
int main ()
{
int m;
while(cin>>n>>m)
{
mem(g, 0);
if (n + m == 0) break;
int u, v;
while(m--)
{
scanf("%d%d", &u, &v);
g[u][v] = 1;
}
toposort();
printf("%d", topo[0]);
for (int i = 1; i < n; i++) printf(" %d", topo[i]);
puts("");
}
return 0;
}
原文:http://blog.csdn.net/sio__five/article/details/18662301