力扣labuladong——一刷day77

本文主要是介绍力扣labuladong——一刷day77，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

图这种数据结构有一些比较特殊的算法，比如二分图判断，有环图无环图的判断，拓扑排序，以及最经典的最小生成树，单源最短路径问题，更难的就是类似网络流这样的问题。 不过以我的经验呢，像网络流这种问题，你又不是打竞赛的，没时间的话就

一、力扣207. 课程表

class Solution {boolean[] onPath;boolean[] visited;boolean hasCycle = false;public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);onPath = new boolean[numCourses];visited = new boolean[numCourses];for(int i = 0; i < numCourses; i ++){traverse(graph, i);}return !hasCycle;}public void traverse(List<Integer>[] graph, int s){if(onPath[s]){hasCycle = true;return;}if(visited[s] || hasCycle){return;}onPath[s] = true;visited[s] = true;for(int a : graph[s]){traverse(graph, a);}onPath[s] = false;}public List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){List<Integer>[] graph = new LinkedList[numCourses];for(int i = 0; i < numCourses; i ++){graph[i] = new LinkedList<>();}for(int[] a : prerequisites){int from = a[1];int to = a[0];graph[to].add(from);}return graph;}
}

这篇关于力扣labuladong——一刷day77的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---