# LeetCode第207题–Course Schedule

## 原题

`2, [[1,0]]`

`2, [[1,0],[0,1]]`

```    public boolean canFinish(int numCourses, int[][] prerequisites) {

}   ```

### 测试数据：

`8, [[1,0],[2,6],[1,7],[5,1],[6,4],[7,0],[0,5],[5,1],[6,4]]`

### 有向图数据结构

```    private class Digraph {

private final int V;

public Digraph(int V) {
this.V = V;
for (int v = 0; v < V; v++) {
}
}

public void addEdge(int v, int w) {
}

public int V() {
return V;
}

}

}```

### 判断有向图中是否有环

onStack[v]=true,记录顶点v出现在这次dfs中，在这次dfs结束后，是onStack[v]=false

```    private class DirectedCycle {
private boolean[] marked;        // marked[v] 顶点v是否被访问过
private boolean[] onStack;       //保存递归调用期间栈上的所有顶点。 onStack[v] = ？顶点v是否在栈中
private boolean hasCycle;       // 有向图中是否环

public DirectedCycle(Digraph G) {
marked = new boolean[G.V()];
onStack = new boolean[G.V()];
hasCycle = false;
for (int v = 0; v < G.V(); v++)   //对图中每一个没有被访问过的点做深度优先遍历
if (!marked[v]) dfs(G, v);
}

/**
* 从v顶点开始做深度优先遍历
*/
private void dfs(Digraph G, int v) {
onStack[v] = true;
marked[v] = true;
for (int w : G.adj(v)) {        //遍历所有顶点v的相连点
if (hasCycle) return;       //如果已经找到一个环就不再dfs
else if (!marked[w]) {      //对每一个未访问过的点继续dfs
dfs(G, w);
} else if (onStack[w]) {    //顶点w在之前的递归调用栈中，并且已经被访问过，构成环
hasCycle = true;
}
}
onStack[v] = false;             //顶点v所有的相连点遍历结束,顶点v退出当前调用栈
}

public boolean hasCycle() {
return hasCycle;
}
}```

### 主方法

```     public boolean canFinish(int numCourses, int[][] prerequisites) {
Digraph G = new Digraph(numCourses);
for (int i = 0; i < prerequisites.length; i++) {
for (int j = 0; j < prerequisites[i].length; j++) {
}
}
DirectedCycle dag = new DirectedCycle(G);

return !dag.hasCycle();

}```

43 篇文章26 人订阅

0 条评论

## 相关文章

1282

### 聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

691

### Educational Codeforces Round 21(A.暴力,B.前缀和,C.贪心)

A. Lucky Year time limit per test:1 second memory limit per test:256 megabytes i...

2797

### 2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

2996

2515

19810

1242

### 3211: 花神游历各国

3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 1042  Solved: 381 ...

2665

### 3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

36911

### BZOJ 3097: Hash Killer I【构造题，思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

1916