generated from threeal/project-starter
-
Notifications
You must be signed in to change notification settings - Fork 1
/
solution.c
64 lines (54 loc) · 1.7 KB
/
solution.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdlib.h>
#include <string.h>
int* findMinHeightTrees(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {
(void)edgesColSize;
if (n == 1) {
*returnSize = 1;
int* returnData = malloc(sizeof(int));
*returnData = 0;
return returnData;
}
int* nextsCountOf = malloc(n * sizeof(int));
memset(nextsCountOf, 0, n * sizeof(int));
for (int i = 0; i < edgesSize; ++i) {
++nextsCountOf[edges[i][0]];
++nextsCountOf[edges[i][1]];
}
int** nextsOf = malloc(n * sizeof(int*));
for (int i = 0; i < n; ++i) {
nextsOf[i] = malloc(nextsCountOf[i] * sizeof(int));
}
int* nextsCounterOf = malloc(n * sizeof(int));
memset(nextsCounterOf, 0, n * sizeof(int));
for (int i = 0; i < edgesSize; ++i) {
nextsOf[edges[i][0]][nextsCounterOf[edges[i][0]]++] = edges[i][1];
nextsOf[edges[i][1]][nextsCounterOf[edges[i][1]]++] = edges[i][0];
}
int* queue = malloc(n * sizeof(int));
int queueBegin = 0;
int queueEnd = 0;
for (int node = 0; node < n; ++node) {
if (nextsCountOf[node] == 1) queue[queueEnd++] = node;
}
while (queueEnd < n) {
for (int i = queueEnd - queueBegin; i > 0; --i) {
for (int j = 0; j < nextsCountOf[queue[queueBegin]]; ++j) {
if (--nextsCounterOf[nextsOf[queue[queueBegin]][j]] == 1) {
queue[queueEnd++] = nextsOf[queue[queueBegin]][j];
}
}
++queueBegin;
}
}
*returnSize = queueEnd - queueBegin;
int* returnData = malloc(*returnSize * sizeof(int));
memcpy(returnData, queue + queueBegin, *returnSize * sizeof(int));
free(queue);
free(nextsCounterOf);
for (int i = 0; i < n; ++i) {
free(nextsOf[i]);
}
free(nextsOf);
free(nextsCountOf);
return returnData;
}