[210] Course Schedule II

哇～～這種題目，真的很靠背捏！！！

跟 [310] Minimum Height Trees 很像，不過這題更像所謂的 Topological Sorting

是說我唸書的時候怎麼感覺好像似乎應該沒有聽過這個啊XD～

（演算法老師表示傷心XD）

所以這題可以用queue是不是被每個node給填滿了來判斷 ＆直接return queue 

感覺好方便XD 沒時間了，我Q亡矣 Q__Q

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize,

int* prerequisitesColSize, int* returnSize) {

int *in = calloc (numCourses, sizeof (int));

int *out = calloc (numCourses, sizeof (int));

int **pTo = calloc (numCourses, sizeof (int*));

int *idxs = calloc (numCourses, sizeof (int));

for (int i=0; i<numCourses;i++)

pTo[i]= calloc (numCourses, sizeof(int));

for (int i=0; i<prerequisitesSize; i++)

{

int node = prerequisites[i][1];

in[prerequisites[i][0]]++;

out[node]++;

pTo[node][idxs[node]++] = prerequisites[i][0];

}

int *queue = calloc (numCourses, sizeof (int));

int qidx=0;

for (int i=0; i<numCourses; i++)

{

if (in[i]==0)

queue[qidx++]=i;

}

int start =0, end =qidx;

while ( end < numCourses && start <end )

{

int diff = end - start;

for (qidx = 0; qidx < diff; qidx++)

{

int node = queue[qidx+start];

for (int i=0; i<idxs[node]; i++)

{

int remove_node = pTo[node][i];

in[remove_node]--;

if (in[remove_node]==0)

queue[end++]=remove_node;

}

}

start += qidx;

}

if (end != numCourses)

{

*returnSize = 0;

return NULL;

}

*returnSize=end;

return queue;

}