My code:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
private int V = 0;
private List<List<Integer>> adj;
public int[] findOrder(int numCourses, int[][] prerequisites) {
V = numCourses;
adj = new ArrayList<List<Integer>>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; i++) {
adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
int[] indegree = new int[V];
for (int i = 0; i < V; i++) {
for (Integer temp : adj.get(i)) {
indegree[temp]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
if (q.size() == 0) {
return new int[0];
}
int counter = 0;
int[] ret = new int[V];
while (!q.isEmpty()) {
Integer node = q.poll();
for (Integer temp : adj.get(node)) {
indegree[temp]--;
if (indegree[temp] == 0) {
q.offer(temp);
}
}
ret[counter++] = node;
}
if (counter != V) {
return new int[0];
}
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] nums = new int[][]{{1,0}};
int[] ret = test.findOrder(2, nums);
System.out.println(ret);
}
}
其實就是 topological sort 實現(xiàn)一下。這是BFS版本
下面是DFS版本：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
private int V = 0;
private List<List<Integer>> adj;
public int[] findOrder(int numCourses, int[][] prerequisites) {
V = numCourses;
adj = new ArrayList<List<Integer>>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; i++) {
adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
boolean[] isVisited = new boolean[V];
HashSet<Integer> set = new HashSet<Integer>();
Stack<Integer> st = new Stack<Integer>();
for (int i = 0; i < V; i++) {
if (!isVisited[i]) {
boolean flag = visit(i, isVisited, set, st);
if (!flag) {
return new int[0];
}
}
}
int[] ret = new int[V];
for (int i = 0; i < V; i++) {
ret[i] = st.pop();
}
return ret;
}
private boolean visit(int node, boolean[] isVisited, HashSet<Integer> set, Stack<Integer> st) {
if (set.contains(node)) {
return false;
}
set.add(node);
for (Integer temp : adj.get(node)) {
boolean flag = visit(temp, isVisited, set, st);
if (!flag) {
return false;
}
}
set.remove(node);
if (!isVisited[node]) {
st.push(node);
}
isVisited[node] = true;
return true;
}
public static void main(String[] args) {
Solution test = new Solution();
int[][] nums = new int[][]{{1,0}};
int[] ret = test.findOrder(2, nums);
System.out.println(ret);
}
}
差不多的思路挠日。就是 isVisited[] 需要在最后設(shè)置成 true
在設(shè)true之前，還需要先判斷下其是否為false柑营，如果是刀诬，再把這個結(jié)點插入到棧中声旺，防止重復(fù)插入元素酷师。
當然贮缕，不應(yīng)該在 visit的地方，加入 if (!isVisited[i]) 的條件问欠，
因為肝匆， 1 - 2互聯(lián)，那么2也需要訪問1時發(fā)現(xiàn)已經(jīng)被訪問過了
這個訪問過了顺献，
可能是 在這次dfs過程中訪問過的旗国，
也可能是之前訪問過的，
無法區(qū)別注整，導(dǎo)致無法判斷是否存在 circle
記住了能曾，topological sort 只是針對于 有向度硝， 無環(huán)圖，有用
今天做題注意力不集中寿冕，不知道怎么了蕊程，心不在焉。
哎驼唱，不多說了藻茂，埋在心里吧。
Anyway, Good luck, Richardo! -- 09/09/2016
