题意：N个火星人说一些火星人是他们的后代，在庭上辈份高的坐前面，低的坐后面，问这N个火星人从前往后的顺序应如何。
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1022
——>>直接进行拓扑排序即可。
#include <cstdio>
#include <vector>
#include <cstring>using namespace std;const int maxn = 100 + 10;
vector<int> G[maxn];
int N, n, c[maxn], topo[maxn];bool dfs(int u)
{c[u] = -1;int cnt = G[u].size();for(int v = 0; v < cnt; v++){if(c[G[u][v]] < 0) return 0;else if(!c[G[u][v]] && !dfs(G[u][v])) return 0;}c[u] = 1;topo[n--] = u;return 1;
}
bool toposort()
{n = N;memset(c, 0, sizeof(c));for(int i = 1; i <= N; i++) if(!c[i])if(!dfs(i)) return 0;return 1;
}
int main()
{int i, v;while(~scanf("%d", &N)){for(i = 1; i <= N; i++){while(~scanf("%d", &v)){if(!v) break;G[i].push_back(v);}}toposort();for(i = 1; i < N; i++)printf("%d ", topo[i]);printf("%d\n", topo[N]);}return 0;
}
也写了个java版的
import java.util.Scanner;
public class Main {static final int maxn = 100 + 10;static int G[][] = new int[maxn][maxn], N, n, topo[] = new int[maxn], c[] = new int[maxn];public static boolean dfs(int u){c[u] = -1;for(int v = 1; v <= N; v++) if(G[u][v] == 1){if(c[v] < 0) return false;if(c[v] == 0 && dfs(v) == false) return false;}c[u] = 1;topo[n--] = u;return true;}public static boolean toposort(){n = N;for(int i = 1; i <= N; i++) c[i] = 0;for(int i = 1; i <= N; i++) if(c[i] == 0)if(dfs(i) == false) return false;return true;}public static void main(String args[]) {Scanner cin = new Scanner(System.in);int i, j;N = cin.nextInt();for(i = 1; i <= N; i++)for(j = 1; j <= N; j++) G[i][j] = 0;for(i = 1; i <= N; i++){while(true){j = cin.nextInt();if(j == 0) break;G[i][j] = 1;}}toposort();for(i = 1; i < N; i++) System.out.print(topo[i]+" ");System.out.println(topo[N]);cin.close();}
}