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 实现一下。这是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[] 需要在最后设置成 true
在设true之前，还需要先判断下其是否为false，如果是，再把这个结点插入到栈中，防止重复插入元素。
当然，不应该在 visit的地方，加入 if (!isVisited[i]) 的条件，
因为， 1 - 2互联，那么2也需要访问1时发现已经被访问过了
这个访问过了，
可能是 在这次dfs过程中访问过的，
也可能是之前访问过的，
无法区别，导致无法判断是否存在 circle
记住了，topological sort 只是针对于 有向， 无环图，有用
今天做题注意力不集中，不知道怎么了，心不在焉。
哎，不多说了，埋在心里吧。
Anyway, Good luck, Richardo! -- 09/09/2016
