Created
April 30, 2016 21:54
-
-
Save jianminchen/5873fc014e806d626807917959e05ea2 to your computer and use it in GitHub Desktop.
Leetcode 210 - course project
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace _210CourseProject | |
{ | |
public class Solution | |
{ | |
static void Main(string[] args) | |
{ | |
} | |
/* | |
* Julia spent time to transfer code to C# code | |
* | |
* Here is the test case to work on: | |
* | |
* int[][] prerequisite | |
* | |
* [[1,0]] | |
There are a total of 2 courses to take. To take course 1 | |
* you should have finished course 0. So the correct course order is [0,1] | |
4, [[1,0],[2,0],[3,1],[3,2]] | |
There are a total of 4 courses to take. To take course 3 | |
* you should have finished both courses 1 and 2. Both courses | |
* 1 and 2 should be taken after you finished course 0. So one | |
* correct course order is [0,1,2,3]. Another correct ordering | |
* is [0,2,1,3]. | |
*/ | |
public int[] findOrder(int numCourses, int[][] prerequisites) { | |
List<List<int>> dpList = new List<List<int>>(); | |
for (int i = 0; i < numCourses; ++i) { | |
dpList.Add(new List<int>()); // dpList[0] is for course 0, and dpList[i] for course i | |
} | |
// get dependency list and indegree | |
int[] indegree = new int[numCourses]; | |
for (int i = 0; i < prerequisites.Length; ++i) { | |
int[] tmpDep = new int[2] { prerequisites[i][0], prerequisites[i][1] }; // add some explanation variable to smooth reading | |
dpList[tmpDep[1]].Add(tmpDep[0]); // (0,1) -> take 0 first, and then take 1 | |
++indegree[tmpDep[0]]; // 0 node adds one more indegree from 1 | |
} | |
// add thoes course first with 0 indegree | |
Queue<int> q = new Queue<int>(); | |
for (int i = 0; i < numCourses; ++i) { | |
if (indegree[i] == 0) | |
q.Enqueue(i); | |
} | |
// take courses | |
int[] result = new int[numCourses]; | |
int count = 0; | |
while (q.Count > 0 ) { // always start from node with indegree value 0 <- make sense | |
// dependency list of node <- course only can be taken after the current node | |
int toTake = q.Dequeue(); | |
result[count++] = toTake; // increment count value <-- use to check if ordering is available at the end | |
foreach (int c in dpList[toTake]) { | |
--indegree[c]; // decrement value of indegree by 1 | |
if (indegree[c] == 0) // check if node c is ready to add to queue <- no indegree | |
q.Enqueue(c); | |
} | |
} | |
if (count != numCourses) | |
return new int[0]; // haven't taken all courses | |
return result; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment