blob: a5cac343d1fbc35f4d5f9c3c611034931462ed62 (
plain)
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
|
// 310. Minimum Height Trees
#include "leetcode.h"
/*
* a tree is an undirected graph in which any two vertices are connected by
* exactly one path. in other words, any connected graph without simple cycles
* is a tee. given a tree of 'n' nodes from 0 to 'n - 1' and an array of 'n - 1'
* edges where 'edges[i] = [ai, bi]' indicates that there is an undirected edge
* between the two nodes 'ai' and 'bi'in the the tree, you can choose any node
* of the tree as the root. return a list of all mht's root labels. you can
* return the answer in any order.
*/
int *findMinHeightTrees(int n, int **edges, int edgesSize, int *edgesColSize,
int *returnSize) {
int *ans = (int *)malloc(sizeof(int) * n);
*returnSize = 0;
if (n == 1) {
(*returnSize)++;
ans[*returnSize - 1] = 0;
return ans;
}
int **graph = (int **)malloc(sizeof(int *) * n);
for (int i = 0; i < n; i++)
graph[i] = (int *)malloc(sizeof(int));
int *col_sizes = (int *)calloc(n, sizeof(int));
for (int i = 0; i < *returnSize; i++) {
int begin = edges[i][0], end = edges[i][1];
col_sizes[begin]++;
graph[begin] = (int *)realloc(graph[begin], sizeof(int) * col_sizes[begin]);
graph[begin][col_sizes[begin] - 1] = end;
col_sizes[end]++;
graph[end] = (int *)realloc(graph[end], sizeof(int) * col_sizes[end]);
graph[end][col_sizes[end] - 1] = begin;
}
int *degrees = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
degrees[i] = col_sizes[i];
if (col_sizes[i] == 1) {
(*returnSize)++;
ans[*returnSize - 1] = i;
}
}
int cnt = n, next = 0;
int *next_level = (int *)malloc(sizeof(int) * n);
while (cnt > 2) {
for (int i = 0; i < *returnSize; i++) {
int end = ans[i];
cnt--;
for (int k = 0; k < col_sizes[end]; k++) {
int begin = graph[end][k];
degrees[begin]--;
if (degrees[begin] == 1)
next_level[next++] = graph[end][k];
}
}
*returnSize = next;
next = 0;
int *tmp = ans;
ans = next_level;
next_level = tmp;
}
return ans;
}
|