diff options
author | Jack Sangdahl <[email protected]> | 2024-12-24 00:05:16 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-24 00:05:16 -0700 |
commit | 48388e0eb7bf87ecb40353794acee7a43557198f (patch) | |
tree | be73c0d3a4122491f1f9a7956c7b0356a77eff65 | |
parent | f124090178e245d8c091689067bf3f566c20781b (diff) | |
download | leetcode-48388e0eb7bf87ecb40353794acee7a43557198f.tar.gz leetcode-48388e0eb7bf87ecb40353794acee7a43557198f.zip |
3203. find minimum diameter after merging two trees
-rw-r--r-- | find_min_diameter_merge_trees.c | 109 | ||||
-rw-r--r-- | find_min_diameter_merge_trees.py | 68 |
2 files changed, 177 insertions, 0 deletions
diff --git a/find_min_diameter_merge_trees.c b/find_min_diameter_merge_trees.c new file mode 100644 index 0000000..a24a927 --- /dev/null +++ b/find_min_diameter_merge_trees.c @@ -0,0 +1,109 @@ +// 3203. Find Minimum Diameter After Merging Two Trees +#include "leetcode.h" + +/* + * there exists two undirected trees with 'n' and 'm' nodes numbered from 0 to + * 'n - 1' and from 0 to 'm - 1', respectively. you are given two 2d integer + * arrays 'edges1', and 'edges2' of lengths 'n - 1' and 'm - 1', respectively, + * where 'edges1[i] = [a_i, b_i]' indicates that thereis an edge between nodes + * 'a_i' and 'b_i' in the first tree, and 'edges2[i] = [u_i, v_i]' indicates + * there is an edge between nodes 'u_i' and 'v_i' in the second tree. you must + * connect one node from the first tree with another node from the second tree + * with an edge. return the minimum possible diameter of the resulting tree. the + * diameter of a tree is the length of the longest path between any two nodes in + * the tree + */ + +enum state { VAL, NEXT }; + +int max_diameter(int **edges, int edgesSize) { + int i, n = edgesSize + 1, queue[n + 1], head = 0, tail = 0; + int hash[n], nodes[(edgesSize << 1) + 1][2], node, ptr = 0; + int cnt, prev, curr, next, diam = 0; + bool *vis = (bool *)calloc(n, sizeof(bool)); + memset(hash, -1, sizeof(hash)); + for (int i = 0; i < edgesSize; i++) { + node = ptr++; + nodes[node][VAL] = edges[i][0]; + nodes[node][NEXT] = hash[edges[i][1]]; + hash[edges[i][1]] = node; + node = ptr++; + nodes[node][VAL] = edges[i][1]; + nodes[node][NEXT] = hash[edges[i][0]]; + hash[edges[i][0]] = node; + } + vis[0] = true; + queue[tail++] = 0; + while (head < tail) { + cnt = tail - head; + while (cnt--) { + curr = queue[head++]; + node = hash[curr]; + while (node >= 0) { + next = nodes[node][VAL]; + node = nodes[node][NEXT]; + if (vis[next]) + continue; + vis[next] = true; + queue[tail++] = next; + } + } + } + memset(vis, false, n); + head = 0; + tail = 1; + queue[0] = curr; + while (head < tail) { + cnt = tail - head; + while (cnt--) { + curr = queue[head++]; + node = hash[curr]; + while (node >= 0) { + next = nodes[node][VAL]; + node = nodes[node][NEXT]; + if (vis[next]) + continue; + vis[next] = true; + queue[tail++] = next; + } + } + if (head < tail) + ++diam; + } + return diam; +} + +int minimumDiameterAfterMerge(int **edges1, int edges1Size, int *edges1ColSize, + int **edges2, int edges2Size, + int *edges2ColSize) { + int d1 = max_diameter(edges1, edges1Size); + int d2 = max_diameter(edges2, edges2Size); + int d3 = (d1 >> 1) + (d1 & 1); + d3 += (d2 >> 1) + (d2 & 1) + 1; + if (d1 < d2) + d1 = d2; + if (d1 < d3) + d1 = d3; + return d1; +} + +int main() { + int e1i1[3][2] = {{0, 1}, {0, 2}, {0, 3}}, e2i1[1][2] = {{0, 1}}; + int e1i2[7][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {2, 5}, {3, 6}, {2, 7}}, + e2i2[7][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {2, 5}, {3, 6}, {2, 7}}; + struct two_d_arr e11, e21, e12, e22; + two_d_arr_init(&e11, 3, 2, e1i1); + two_d_arr_init(&e21, 1, 2, e2i1); + two_d_arr_init(&e12, 7, 2, e1i2); + two_d_arr_init(&e22, 7, 2, e2i2); + printf("%d\n", + minimumDiameterAfterMerge(e11.arr, e11.row_size, e11.col_size, e21.arr, + e21.row_size, e21.col_size)); // expect: 3 + printf("%d\n", + minimumDiameterAfterMerge(e12.arr, e12.row_size, e12.col_size, e22.arr, + e22.row_size, e22.col_size)); // expect: 5 + two_d_arr_free(&e11); + two_d_arr_free(&e21); + two_d_arr_free(&e12); + two_d_arr_free(&e22); +} diff --git a/find_min_diameter_merge_trees.py b/find_min_diameter_merge_trees.py new file mode 100644 index 0000000..d5f5d2f --- /dev/null +++ b/find_min_diameter_merge_trees.py @@ -0,0 +1,68 @@ +# 3203. Find Minimum Diameter After Merging Two Trees + +""" +there exists two undirected trees with 'n' and 'm' nodes numbered from 0 to +'n - 1' and from 0 to 'm - 1', respectively. you are given two 2d integer +arrays 'edges1', and 'edges2' of lengths 'n - 1' and 'm - 1', respectively, +where 'edges1[i] = [a_i, b_i]' indicates that thereis an edge between nodes +'a_i' and 'b_i' in the first tree, and 'edges2[i] = [u_i, v_i]' indicates +there is an edge between nodes 'u_i' and 'v_i' in the second tree. you must +connect one node from the first tree with another node from the second tree +with an edge. return the minimum possible diameter of the resulting tree. the +diameter of a tree is the length of the longest path between any two nodes in +the tree +""" + + +class Solution(object): + def minimumDiameterAfterMerge(self, edges1, edges2): + """ + :type edges1: List[List[int]] + :type edges2: List[List[int]] + :rtype: int + """ + + def farthest(hash, i): + n = len(hash) + bfs = [i] + vis = [0] * n + vis[i] = 1 + res, diam = -1, -1 + for i in bfs: + for j in hash[i]: + if vis[j] == 0: + vis[j] = vis[i] + 1 + bfs.append(j) + if vis[j] > diam: + res = j + diam = vis[j] + return res, diam - 1 + + def diameter(edges): + if not edges: + return 0, 0, 0 + n = len(edges) + 1 + hash = [[] for i in range(n)] + for i, j in edges: + hash[i].append(j) + hash[j].append(i) + v1, d = farthest(hash, 0) + v2, d = farthest(hash, v1) + return d, v1, v2 + + d1, i, j = diameter(edges1) + d2, i, j = diameter(edges2) + return max(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.minimumDiameterAfterMerge(edges1=[[0, 1], [0, 2], [0, 3]], edges2=[[0, 1]]) + ) + print( + obj.minimumDiameterAfterMerge( + edges1=[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 6], [2, 7]], + edges2=[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 6], [2, 7]], + ) + ) |