[310] Minimum Height Trees

什麼！竟然會超時嗎！！！可惡我完美的recursive 啊XD！！！！！

先貼個超時版本Orz

原本想寫的是先把leaf 拿掉的QQ

/**

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

*/

int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {

if (edgesSize == 0)

{

*returnSize=1;

int *ret = calloc (1, sizeof(int)*1);

ret[0]=n-1;

return ret;

}

else if (edgesSize==1)

{

*returnSize=2;

int *ret = calloc (2, sizeof(int)*2);

ret[0]=edges[0][0];

ret[1]=edges[0][1];

return ret;

}

int *count = calloc (n, sizeof(int)*n);

int max = 0;

int new_edge = edgesSize;

int new_edge_count=0;

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

{

count[edges[i][0]]++;

count[edges[i][1]]++;

if (count[edges[i][0]] > count[max])

max = edges[i][0];

if (count[edges[i][1]] > count[max])

max = edges[i][1];

}

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

{

if (count[edges[i][0]]==1 || count [edges[i][1]]==1)

{

new_edge--;

}

else

{

edges[new_edge_count][0]= edges[i][0];

edges[new_edge_count][1]= edges[i][1];

new_edge_count++;

}

}

if (new_edge==0)

return findMinHeightTrees(max+1,edges, 0, edgesColSize, returnSize);

else

return findMinHeightTrees(n, edges, new_edge_count, edgesColSize, returnSize);

}

威～～～～什麼不能超時XD

（a few days later......)

咳～拖好多天Orz 怎麼寫是怎麼不順利Orz 本想用linked list node 去用的

但也沒有想清楚，最後都不知道自己在幹嘛(痛哭）

後來還是放棄了，找了個用雙重array 開下去的版本！

速度好像很慢！ 但看了超級快的版本發現，我根本看不懂Orz

為什麼node 們可以 nodeA ^= nodeB 這樣就紀錄了它們彼此之間的 edge 呢？

一定是我漏了什麼東西吧........(可能是漏了很多的聰明才智嗚嗚嗚)

就這樣吧～已經花太多時間在這題上面了啊啊啊啊啊啊～～～～（奔入雨中）

/**

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

*/

int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {

if (n==1)

{

*returnSize=1;

int *ret = calloc (*returnSize, sizeof(int));

ret[0]= 0;

return ret;

}

int *count = calloc (n, sizeof(int));

int **list = calloc (n, sizeof(int*));

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

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

{

count[edges[i][0]]++;

count[edges[i][1]]++;

}

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

list[i]= calloc (count[i], sizeof(int));

free(count);

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

{

int idx = edges[i][0];

list[idx][idxs[idx]] = edges[i][1];

idxs[idx]++;

idx = edges[i][1];

list[idx][idxs[idx]] = edges[i][0];

idxs[idx]++;

}

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

int q_idx=0;

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

if (idxs[i]==1)

queue[q_idx++]= i ;

int start=0;

int end = q_idx;

while (q_idx < n)

{

for (int i=start; i< end; i++)

{

int remove_node = queue[i] ;

int remove_edge = list[remove_node][0];

// idxs[remove_node]=0;

// free(list[remove_node]);

for (int j=0;j<idxs[remove_edge];j++)

{

if (list[remove_edge][j]==remove_node)

{

list[remove_edge][j] = list[remove_edge][--idxs[remove_edge]];

break;

}

}

if (idxs[remove_edge] == 1)

queue[q_idx++]= remove_edge ;

}

start = end;

end= q_idx;

}

*returnSize = end - start;

int *ret = calloc (*returnSize, sizeof(int));

ret[0]= queue[q_idx-1];

if (*returnSize > 1)

ret[1]= queue[q_idx-2];

return ret;

}