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

Jan. 26, 2022

Here is the link.

C# | DFS algorithm | Study Leetcode discuss C# code | Jan. 26, 2022

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
The algorithm can be modelled as a simple directed unweighted graph to solve. There are two approaches, one is to work on nodes with indegree 0 first, and remove edges connected to those nodes. Repeat the process. I called it BFS, and the other one is to apply depth first search algorithm.

Assume that the graph may have cycle, it is challenge to solve the problem using DFS and also detect cycle in the same time. I chose to study one of discuss post instead after I studied DFS solution shared by Leetcode solution shared only for premium users. Here is the post.

Code study | Code review | DFS algorithm base case | Play with test case

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.

case 2: 4, [[1,0],[2,0],[3,1],[3,2]]
output: [0,2,1,3]

A few things to look into more carefully, write down in the following:

1. Only need to find one path. So in DFS, no need to apply backtracking; I like to question this statement in the comment written by the user: https://leetcode.com/bacon/;
2. Use private variables, so that function runDepthFirstSearch has less than five arguments. Two are private variables to store courses taken in the order to meet prerequisite requirement.
3. Work on test case II in main function, start from course 3 to run DFS, 3 -> 1 -> 0, so how to mark those three nodes using isVisited and isAdded? Think about more carefully in the design stage.
4. More on step 3, if first visit is node 3, and then start DFS from node 3, mark isVisited[3] = true, and let the search go through 1 and then go through 0. Node 0 is found and then isAdded[0] = true, reset all isVisited to false; isVisited is helpful to detect cycle.
5. More on step 4, isAdded is helpful to terminate DFS search as a base case.
6. More on step 3, path A: from 1 -> 0, path B: from 3->1->0, node 1 will be visited more than once, so isVisited has to be reset all the time. For example, if path A is checked first, isVisited[1] should be false again, then path B can be examined properly.

Improvements:

1. DFS algorithm - make base case the first statement - clear and not hidden in the if the statement, and also save cost to avoid visit removed edges in the graph.
2. Move isVisited variable inside for loop.

Challenge to be expert on algorithm | Take risk | Do my best
It takes time for me to ask questions on reviewing C# code written by others. I do think that this DFS approach is very good example for me to learn from my own experience as an excellent reviewer with patience to work on a simple test case.

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]; // move into for loop 
            var isAdded   = new bool[numCourses];

            for (int i = 0; i < numCourses; i++)
            {
			    var isVisited = new bool[numCourses];
				
                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(isAdded[courseId]) // I added the statement - this should be base case, make it clear!
            {
                return true;    
            }
            
            if (isVisited[courseId]) // detect a cycle - quit!
            {
                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;
        }
    }
}