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 ArrayList<List<Integer>> adj;
public boolean canFinish(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.isEmpty()) {
return false;
}
int counter = 0;
while (!q.isEmpty()) {
Integer node = q.poll();
for (Integer temp : adj.get(node)) {
indegree[temp]--;
if (indegree[temp] == 0) {
q.offer(temp);
}
}
counter++;
}
if (counter != V) {
return false;
}
else {
return true;
}
}
}
这道题目的本质在于，如何判断一个图中是否存在 circle
然后有两种方法：
BFS, DFS
我个人更偏爱于 BFS
首相介绍下，什么是 topological sort
就是将一堆有dependency 的结点按照先后顺序输出出来。
这个介绍的不错。：
http://www.stoimen.com/blog/2012/10/01/computer-algorithms-topological-sort-of-a-graph/
必须是有向无环图 DAG
如何表示一个有向图。可以是链表，也可以是稀疏矩阵
一个DAG，他一定至少有一个 入度为0的结点，一个出度为0的结点。
所以，如果我们从入度入手，先把入度为0的结点删除了。
然后再把删除后重新成为入度为0的结点删除了。
依次循环，最后，如果，删除的结点个数不等于图总结点个数，那么，就是有环图。
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
这就是上面这个算法的思想。
写的还是很巧妙地。
下面说下 DFS
借鉴了这个思想：
http://www.geeksforgeeks.org/topological-sorting/
如果用 DFS实现 topological sort
其实相比于BFS，更简单，只用一味地DFS就行。
但是如果用来判断是否有环，就麻烦了。
于是我们需要维护一个set，然后每次进入一个节点，开始DFS
把访问过的结点加入到set中，如果在这次dfs中，之后又再次碰到了这个点，那么就说明有重复，有环，就报错。
如果没问题，退回到这个结点的时候，千万记得，把这个结点从set中删去，因为其他路径可能再次包含这个结点
同时，还需要维护一个总的 布尔数组，来表示哪些结点已经被访问过了，不用再进行判断了。
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 ArrayList<List<Integer>> adj;
public boolean canFinish(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];
for (int i = 0; i < V; i++) {
if (!isVisited[i]) {
boolean flag = visit(i, isVisited, new HashSet<Integer>());
if (!flag) {
return false;
}
}
}
return true;
}
private boolean visit(int node, boolean[] isVisited, HashSet<Integer> set) {
if (set.contains(node)) {
return false;
}
set.add(node);
isVisited[node] = true;
for (Integer temp : adj.get(node)) {
boolean flag = visit(temp, isVisited, set);
if (!flag) {
return false;
}
}
set.remove(node);
return true;
}
}
reference:
https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions
Anyway, Good luck, Richardo! -- 09/09/2016
My code:
public class Solution {
private Map<Integer, Set<Integer>> adj;
private int[] degree;
public boolean canFinish(int numCourses, int[][] prerequisites) {
adj = new HashMap<Integer, Set<Integer>>();
degree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int src = prerequisites[i][1];
int dest = prerequisites[i][0];
if (!adj.containsKey(src)) {
adj.put(src, new HashSet<Integer>());
}
if (!adj.get(src).contains(dest)) {
adj.get(src).add(dest);
degree[dest]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (degree[i] == 0) {
q.offer(i);
}
}
int total = 0;
while (!q.isEmpty()) {
Integer curr = q.poll();
total++;
if (adj.containsKey(curr)) {
for (Integer nei : adj.get(curr)) {
degree[nei]--;
if (degree[nei] == 0) {
q.offer(nei);
}
}
}
}
return total == numCourses;
}
}
要注意，可能输入边会重复, 所以要用set，并且初始化图时要检查。
而且， [1] 是 src, [0] 是 dest
Anyway, Good luck, Richardo! -- 10/17/2016
