Leetcode discuss: 210. Course Schedule II | DFS | Learn from others | Challenging work

 Jan. 26, 2022

Here is the link.

Jan. 26, 2022

Introduction
It is so interesting to read C# code with meaningful comments and good variable names. I did learn a few things from studying one of C# discuss post using DFS. What I can learn from 20 minutes to read and also running C# code? I like to write a post first, and then come back to review later.

C# | DFS algorithm | Simple to detect cycle | Style talk
Two variables are added to help DFS algorithm, isVisited and isAdded.

I like to learn from a few discuss using C# and see what I can do better this time.

The following code passes online judge.

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

namespace _210_course_schedule_2
{
    class Program
    {
        static void Main(string[] args)
        {
            // case 2: 4, [[1,0],[2,0],[3,1],[3,2]]
            // output: [0,2,1,3]
            var case2 = new int[4][];
            case2[0] = new int[] { 1, 0 };
            case2[1] = new int[] { 2, 0 };
            case2[2] = new int[] { 3, 1 };
            case2[3] = new int[] { 3, 2 };

            var test = new Program();
            var output = test.FindOrder(4, case2);
            Debug.Assert(string.Join("->", output).CompareTo("0->2->1->3") == 0);
        }

        // Style talk: Using private variables, good comment about DFS, cycle detection, meaningful variable names
        // do not need backtracking because we only need one solution.
        private int[] coursesInOrder;
        private int index = 0;

        /// <summary>
        /// Jan. 26, 2022
        /// DFS algorithm
        /// Learn C# code from https://leetcode.com/problems/course-schedule-ii/discuss/294815/C-DFS
        /// </summary>
        /// <param name="numCourses"></param>
        /// <param name="prerequisites"></param>
        /// <returns></returns>
        public int[] FindOrder(int numCourses, int[][] prerequisites)
        {
            coursesInOrder = new int[numCourses];

            var adjacencyMatrix = new HashSet<int>[numCourses]; // adjacencyMatrix is better name compared to takenFirst

            for (int i = 0; i < numCourses; i++)
            {
                adjacencyMatrix[i] = new HashSet<int>();
            }

            foreach (var fromTo in prerequisites)
            {
                var from = fromTo[0];
                var to   = fromTo[1];

                adjacencyMatrix[from].Add(to); // from, to variables are more meaningful than first, next
            }

            var isVisited = new bool[numCourses];
            var isAdded   = new bool[numCourses];

            for (int i = 0; i < numCourses; i++)
            {
                if (isAdded[i])
                {
                    continue;
                }

                var noCyclic = runDepthFirstSearch(i, adjacencyMatrix, isVisited, isAdded);

                if (!noCyclic)
                {
                    return new int[0];
                }
            }

            return coursesInOrder;
        }

        /// <summary>
        /// Jan. 26, 2022
        /// Return false - no cycle in the graph
        /// true - no cycle
        /// </summary>
        /// <param name="courseId"></param>
        /// <param name="adjacencyMatrix"></param>
        /// <param name="isVisited"></param>
        /// <param name="isAdded"></param>
        /// <returns></returns>
        private bool runDepthFirstSearch(int courseId, HashSet<int>[] adjacencyMatrix, bool[] isVisited, bool[] isAdded)
        {
            if (isVisited[courseId])
            {
                return false;
            }

            isVisited[courseId] = true;
            var nextCourses = adjacencyMatrix[courseId];

            foreach (var next in nextCourses)
            {
                var noCycle = runDepthFirstSearch(next, adjacencyMatrix, isVisited, isAdded);
                if (!noCycle)
                {
                    return false;
                }
            }

			// backtracking is challenging, think about more since I did not write original C# code - Jan. 26, 2022
            if (!isAdded[courseId]) // play with if statement, argue that not visited must be not added ? not true
            {
                coursesInOrder[index] = courseId;
                index++;
                isAdded[courseId] = true;
            }

            isVisited[courseId] = false; // play with this reset, why?

            return true;
        }
    }
}