uva 10305 Ordering Tasks(拓扑排序)

拓扑排序。

先理一下思路吧：

根据输入建立一个有向图表，然后用一个一维数组vis来记录1~n中某个元素是否已经被访问过。

然后从1~n进行循环,如果vis[i]没有被访问过,就对i做dfs搜索。因为是拓扑排序，所以从i一定可以到达排序的最后一个元素，将i到拓扑排序的最后一个元素在dfs的时候记为已经访问过，即vis[i~最后一个元素]=1。

在dfs的过程中,一定会到达最后一个元素，所以建立一个一维数组topo，和变量t=n。每次dfs，让topo[t--]=u。因为，递归的过程是逆序，递归的终点是拓扑排序的最后一个元素，所以要放在topo的最后面。

import java.util.Arrays; import java.util.Scanner; public class Main { static int n,m,t; static int[] vis; static int[][] A; static int[] topo; public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(true){ n = scan.nextInt(); m = scan.nextInt(); if(n==0&&m==0)break; A = new int[n+1][n+1]; vis = new int[n+1]; topo = new int[n+1]; for(int i=0;i<m;i++){ int u = scan.nextInt(); int v = scan.nextInt(); A[u][v] = 1; } t = n; for(int u=1;u<=n;u++){ if(vis[u]==0){ dfs(u); } } for(int i=1;i<=n;i++){ System.out.print(topo[i]+" "); } System.out.println(); } } public static void dfs(int u){ vis[u] = -1; for(int v=1;v<=n;v++){ if(A[u][v]==1){ if(vis[v]<0)return; if(vis[v]==0){ dfs(v); } } } topo[t--] = u; vis[u] = 1; } }