Leetcode 207 - course project

Leetcode207CourseProject.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _207CourseProject
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /*
         * Leetcode 207
         */
        public class Solution
        {
            public bool canFinish(int numCourses, int[][] prerequisites) {
                if (numCourses < 0) {
                  return false; 
                }

                if (prerequisites == null || prerequisites.Length == 0) {
                  return true;
                }

                List<List<int>> dpList = getDependencyList(numCourses, prerequisites);

                bool[] visited = new bool[numCourses];

                int cur = 0;
                while (true) { // in each iteration, a dfs is conducted
                  while (cur < visited.Length && visited[cur]) {
                    ++cur; // get next unvisited node
                  }

                  if (cur == numCourses) {
                    break; // finished traversing
                  }

                  HashSet<int> curActive = new HashSet<int>();

                  if (dfsHelperHasCycle(cur, dpList, curActive, visited)) {
                    return false;
                  }
                }

                return true;
            }

            private List<List<int>> getDependencyList(int numCourses,
                int[][] prerequisites) 
            {
                List<List<int>> dpList = new List<List<int>>();

                for (int i = 0; i < numCourses; ++i) {
                  dpList.Add(new List<int>());         
                }

                for (int i = 0; i < prerequisites.Length; ++i) {
                  dpList[prerequisites[i][1]].Add(prerequisites[i][0]);
                }

                return dpList;
           }

           private bool dfsHelperHasCycle(
                int cur, 
                List<List<int>> dpList,
                HashSet<int> curActive, 
                bool[] visited) 
           {
                visited[cur] = true;
                curActive.Add(cur);

                foreach (int nb in dpList[cur]) {
                  if (curActive.Contains(nb)) {
                    return true; // has cycle
                  }
                }

                foreach (int nb in dpList[cur]) {
                  if (!visited[nb] && dfsHelperHasCycle(nb, dpList, curActive, visited)) {
                    return true;
                  }
                }

                curActive.Remove(cur); // restore such that it will not affect other paths
                return false;
           }
        }
    }
}