aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-24 00:05:16 -0700
committerJack Sangdahl <[email protected]>2024-12-24 00:05:16 -0700
commit48388e0eb7bf87ecb40353794acee7a43557198f (patch)
treebe73c0d3a4122491f1f9a7956c7b0356a77eff65
parentf124090178e245d8c091689067bf3f566c20781b (diff)
downloadleetcode-48388e0eb7bf87ecb40353794acee7a43557198f.tar.gz
leetcode-48388e0eb7bf87ecb40353794acee7a43557198f.zip
3203. find minimum diameter after merging two trees
-rw-r--r--find_min_diameter_merge_trees.c109
-rw-r--r--find_min_diameter_merge_trees.py68
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]],
+ )
+ )