[207] Course Schedule

呃啊～～～～（拔頭髮）

選課之間的先後關係～可以看成是檢查 graph 裡面有沒有loop

如果有loop就是無法完成選課～（修A之前要先修B，修B之前要先修A)

為了這題卡住好幾天，雖然寫出來效能不佳，也不能再拖下去了XD

先這樣吧 QQ

據說是一個Kahn's algorithm

1. 先算每個node的indegree 數目

2. 將indegree==0的人加進queue

3. 從queue取一個出來 , 用一個變數紀錄共取了幾個node出來  ->

被取出來的人是沒有indegree的，但可能有outdegree. 所以將它指出去的人一個一個檢查，如果它們扣掉目前這支edge之後，也變成indegree=0的話，就把被檢查的node也加進queue. 同時把這些被檢查的node的indegree 數目減一。因為我們要把指去它的人拿掉了～

4. 檢查取出來的node數 是不是等於 總共的number node數

相同的話表示沒有loop

寫這個解釋覺得好複雜，這個題目也太難了吧！！！！！！

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){

int *indegree = malloc (sizeof(int)*numCourses);

int **record = malloc (sizeof(int*)*numCourses);

int *num = malloc (sizeof(int)*numCourses);

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

{

num[i]=0;

indegree[i]= 0;

record[i]= malloc(sizeof(int)*numCourses);

}

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

{

int idx=prerequisites[i][0];

record[prerequisites[i][1]][num[prerequisites[i][1]]]=prerequisites[i][0];

indegree[idx]+=1;

num[prerequisites[i][1]]++;

}

//take indegree 0 into queue

int *queue = malloc (sizeof(int)*numCourses);

int queueIdx=0;

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

{

if (indegree[i]==0)

queue[queueIdx++]=i;

}

int deQcount=0;

while (queueIdx >0)

{

deQcount++;

int idx=queue[--queueIdx];

for (int j=0;j<num[idx];j++)

{

int minusIdx=record[idx][j];

indegree[minusIdx]--;

if (indegree[minusIdx] == 0)

queue[queueIdx++]=minusIdx;

}

}

return (deQcount==numCourses);

}