Topological Order--- course schedule
Question
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair
[0, 1], indicates that to take course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
Classification& Assumption
Graph Representation
Vertex: course
Edge: dependency course
High Level
Problem definition
find a topological order in a directed graph
choose traversal algorithm
dfs2 & bfs
Middle Level
Method 1
graph representation:
vertex: course, int[]
edge: dependency course, Set<Integer>
visited:
enum State
Method 3
graph representation:
wrapped class
visited?
enum State? or not
set of preCourse
set of nextCourse
TC & SC
TC: O(|V|+ |E|)
SC: O(|V|)
Code: Method 3:
class Solution {
class Course {
int courseNumber;
Set<Course> prevCourse;
Set<Course> nextCourse;
boolean visited;
boolean visiting;
public Course(int course) {
this.courseNumber = course;
this.prevCourse = new HashSet<>();
this.nextCourse = new HashSet<>();
this.visited = false;
this.visiting = false;
}
@Override
public int hashCode(){
int hashCode = this.courseNumber * 31 + 31;
return hashCode;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) {
return false;
}
Course that = (Course) obj;
return this.courseNumber == that.courseNumber;
}
}
class ReturnType{
boolean isCycle = true;
int count;
public ReturnType(boolean isCycle, int count) {
this.isCycle = isCycle;
this.count = count;
}
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
// sanity check
// build graph
Map<Integer, Course> graph = buildGraph(numCourses, prerequisites);
// Set<Course> init = buildInit(graph);
int globalCount = 0;
for (int courseNumber: graph.keySet()) {
Course init = graph.get(courseNumber);
// if (init.prevCourse == null) {
if (init.prevCourse.isEmpty()){
ReturnType curResult = dfs(init, graph);
if (curResult.isCycle == true) {
return false;
}
globalCount += curResult.count;
}
}
return globalCount == numCourses;
}
private ReturnType dfs(Course init, Map<Integer, Course> graph) {
if (init.visiting == true) {
return new ReturnType(true, 0);
}
if (init.visited == true) { // 注意这两个的顺序，如果你不是exclusive的状态
return new ReturnType(false, 0);
}
init.visiting = true;
int count = 1;
for (Course next: init.nextCourse) {
ReturnType nextResult = dfs(next, graph);
if (nextResult.isCycle == true) {
return new ReturnType(true, 0);
}
count += nextResult.count;
}
init.visited = true; // 注意，这里是先标visiting，然后再标visited，否则会出错。。。
init.visiting = false; // 如果没有这一行，visited要在前面,
return new ReturnType(false, count);
}
private Map<Integer, Course> buildGraph(int numCourses, int[][] prerequisites) {
Map<Integer, Course> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new Course(i));
}
for (int[] depe: prerequisites) {
int nextCourse = depe[0];
int prevCourse = depe[1];
Course next = graph.get(nextCourse);
Course prev = graph.get(prevCourse);
next.prevCourse.add(prev);
prev.nextCourse.add(next);
}
return graph;
}
}Method 3 dfs with enum
class Solution {
class Course {
int courseNumber;
Set<Course> prevCourse;
Set<Course> nextCourse;
State state;
// = State.UNVISITED;
public Course(int course) {
this.courseNumber = course;
this.prevCourse = new HashSet<>();
this.nextCourse = new HashSet<>();
this.state = State.UNVISITED;
}
@Override
public int hashCode(){
int hashCode = this.courseNumber * 31 + 31;
return hashCode;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) {
return false;
}
Course that = (Course) obj;
return this.courseNumber == that.courseNumber;
}
}
class ReturnType{
boolean isCycle = true;
int count;
public ReturnType(boolean isCycle, int count) {
this.isCycle = isCycle;
this.count = count;
}
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
// sanity check
// build graph
Map<Integer, Course> graph = buildGraph(numCourses, prerequisites);
// Set<Course> init = buildInit(graph);
int globalCount = 0;
for (int courseNumber: graph.keySet()) {
Course init = graph.get(courseNumber);
if (init.prevCourse.isEmpty()){
ReturnType curResult = dfs(init, graph);
// System.out.println(curResult.count);
if (curResult.isCycle == true) {
return false;
}
globalCount += curResult.count;
}
}
return globalCount == numCourses;
}
private ReturnType dfs(Course init, Map<Integer, Course> graph) {
if (init.state == State.VISITED) {
return new ReturnType(false, 0);
}
if (init.state == State.VISITING) { // 注意这两个的顺序，如果你不是exclusive的状态
return new ReturnType(true, 0);
}
init.state = State.VISITING;
int count = 1;
for (Course next: init.nextCourse) {
ReturnType nextResult = dfs(next, graph);
// System.out.println(nextResult.count);
// System.out.println(nextResult.isCycle);
if (nextResult.isCycle == true) {
return new ReturnType(true, 0);
}
count += nextResult.count;
}
init.state = State.VISITED; // 注意，这里是先标visiting，然后再标visited，否则会出错。。。
// System.out.println(count);
return new ReturnType(false, count);
}
private Map<Integer, Course> buildGraph(int numCourses, int[][] prerequisites) {
Map<Integer, Course> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new Course(i));
}
for (int[] depe: prerequisites) {
int nextCourse = depe[0];
int prevCourse = depe[1];
Course next = graph.get(nextCourse);
Course prev = graph.get(prevCourse);
next.prevCourse.add(prev);
// System.out.println(next.prevCourse);
prev.nextCourse.add(next);
// System.out.println(prev.nextCourse);
}
return graph;
}
private enum State {
VISITED,
VISITING,
UNVISITED,
}
}Method 3 with bfs
class Solution {
class Course {
int courseNumber;
Set<Course> prevCourse;
Set<Course> nextCourse;
State state;
int preCourseNumber;
public Course(int course) {
this.courseNumber = course;
this.prevCourse = new HashSet<>();
this.nextCourse = new HashSet<>();
this.state = State.UNVISITED;
this.preCourseNumber = 0;
}
@Override
public int hashCode(){
int hashCode = this.courseNumber * 31 + 31;
return hashCode;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (this.getClass() != obj.getClass()) {
return false;
}
Course that = (Course) obj;
return this.courseNumber == that.courseNumber;
}
}
class ReturnType{
boolean isCycle = true;
int count;
public ReturnType(boolean isCycle, int count) {
this.isCycle = isCycle;
this.count = count;
}
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
// sanity check
// build graph
Map<Integer, Course> graph = buildGraph(numCourses, prerequisites);
ReturnType result = bfs(graph);
return result.count == numCourses;
}
private ReturnType bfs(Map<Integer, Course> graph) {
Queue<Course> queue = new ArrayDeque<>();
int count = 0;
for (int courseNumber: graph.keySet()) {
Course cur = graph.get(courseNumber);
if (cur.prevCourse.isEmpty()) {
count++;
queue.offer(cur);
}
}
boolean isCycle = false;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Course cur = queue.poll();
for (Course next: cur.nextCourse) {
next.preCourseNumber--;
if (next.preCourseNumber == 0) {
count++;
queue.offer(next);
}
}
}
}
return new ReturnType(isCycle, count);
}
private Map<Integer, Course> buildGraph(int numCourses, int[][] prerequisites) {
Map<Integer, Course> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new Course(i));
}
for (int[] depe: prerequisites) {
int nextCourse = depe[0];
int prevCourse = depe[1];
Course next = graph.get(nextCourse);
next.preCourseNumber++;
Course prev = graph.get(prevCourse);
next.prevCourse.add(prev);
prev.nextCourse.add(next);
}
return graph;
}
private enum State {
VISITED,
VISITING,
UNVISITED,
}
}Last updated