Course Schedule: N*DFS

Performing a DFS can be expensive, and performing N times a DFS can be dauting, but the thing to keep in mind is the pruning. In this problem, we have a very nice condition that we perform the DFS if and only if the current course has not been processed before. Turns out that on average this will still be linear, perhaps a 2N execution time (N=10^5), but still doable. Hence the trick is to have 3 hashtables: 1/ the courses that have been taken, 2/ the list of course --> pre-requisites and 3/ the list of course --> post-requisite. Then call the DFS for each node, and check if all have been visited. Code is down below, cheers and Happy MLK Day!!! ACC

Course Schedule - LeetCode

207. Course Schedule

Medium

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 course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

 

Constraints:

• 1 <= numCourses <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Accepted

764,954

Submissions

1,706,492

public bool CanFinish(int numCourses, int[][] prerequisites)
{
    Hashtable htPre = new Hashtable();
    Hashtable htPos = new Hashtable();

    for (int i = 0; i < prerequisites.Length; i++)
    {
        int pre = prerequisites[i][1];
        int pos = prerequisites[i][0];

        if (!htPre.ContainsKey(pos)) htPre.Add(pos, new Hashtable());
        Hashtable tPre = (Hashtable)htPre[pos];
        if (!tPre.ContainsKey(pre)) tPre.Add(pre, true);

        if (!htPos.ContainsKey(pre)) htPos.Add(pre, new Hashtable());
        Hashtable tPos = (Hashtable)htPos[pre];
        if (!tPos.ContainsKey(pos)) tPos.Add(pos, true);
    }

    Hashtable coursesTaken = new Hashtable();
    for (int n = 0; n < numCourses; n++)
    {
        if (coursesTaken.Count == numCourses) break;
        TryCourse(n, htPre, htPos, coursesTaken);
    }

    return coursesTaken.Count == numCourses;
}

public void TryCourse(int course,
                        Hashtable htPre,
                        Hashtable htPos,
                        Hashtable coursesTaken)
{
    if (coursesTaken.ContainsKey(course)) return;

    if (htPre.ContainsKey(course))
    {
        Hashtable preCourses = (Hashtable)htPre[course];
        foreach (int n in preCourses.Keys)
            if (!coursesTaken.ContainsKey(n)) return;
    }
    coursesTaken.Add(course, true);

    if (htPos.ContainsKey(course))
    {
        Hashtable posCourses = (Hashtable)htPos[course];
        foreach (int n in posCourses.Keys)
            TryCourse(n, htPre, htPos, coursesTaken);
    }
}