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;
}
}
}
這道題目的本質(zhì)在于及志，如何判斷一個圖中是否存在 circle
然后有兩種方法：
BFS, DFS
我個人更偏愛于 BFS
首相介紹下潜的，什么是 topological sort
就是將一堆有dependency 的結(jié)點(diǎn)按照先后順序輸出出來。
這個介紹的不錯则果。：
http://www.stoimen.com/blog/2012/10/01/computer-algorithms-topological-sort-of-a-graph/
必須是有向無環(huán)圖 DAG
如何表示一個有向圖厉亏〖叟酰可以是鏈表，也可以是稀疏矩陣
一個DAG让蕾，他一定至少有一個 入度為0的結(jié)點(diǎn)浪规，一個出度為0的結(jié)點(diǎn)。
所以涕俗，如果我們從入度入手罗丰，先把入度為0的結(jié)點(diǎn)刪除了。
然后再把刪除后重新成為入度為0的結(jié)點(diǎn)刪除了再姑。
依次循環(huán)萌抵，最后，如果，刪除的結(jié)點(diǎn)個數(shù)不等于圖總結(jié)點(diǎn)個數(shù)绍填，那么霎桅，就是有環(huán)圖。
http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
這就是上面這個算法的思想讨永。
寫的還是很巧妙地滔驶。
下面說下 DFS
借鑒了這個思想：
http://www.geeksforgeeks.org/topological-sorting/
如果用 DFS實(shí)現(xiàn) topological sort
其實(shí)相比于BFS，更簡單卿闹，只用一味地DFS就行揭糕。
但是如果用來判斷是否有環(huán)，就麻煩了锻霎。
于是我們需要維護(hù)一個set著角，然后每次進(jìn)入一個節(jié)點(diǎn)，開始DFS
把訪問過的結(jié)點(diǎn)加入到set中旋恼，如果在這次dfs中吏口，之后又再次碰到了這個點(diǎn)，那么就說明有重復(fù)冰更，有環(huán)产徊，就報(bào)錯。
如果沒問題蜀细，退回到這個結(jié)點(diǎn)的時(shí)候舟铜，千萬記得，把這個結(jié)點(diǎn)從set中刪去审葬，因?yàn)槠渌窂娇赡茉俅伟@個結(jié)點(diǎn)
同時(shí)深滚，還需要維護(hù)一個總的 布爾數(shù)組，來表示哪些結(jié)點(diǎn)已經(jīng)被訪問過了涣觉，不用再進(jìn)行判斷了痴荐。
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;
}
}
要注意，可能輸入邊會重復(fù), 所以要用set官册，并且初始化圖時(shí)要檢查生兆。
而且， [1] 是 src, [0] 是 dest
Anyway, Good luck, Richardo! -- 10/17/2016
