aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-28 21:46:45 -0600
committerJack Sangdahl <[email protected]>2025-05-28 21:46:45 -0600
commita950959b8a433478ab7a33b34fb1f4d2d7bafcb8 (patch)
tree24412c02ea26a55871ac3af780c34936d7247b53
parentb8408a05bc8c1d6fb74b4bcbb030caddcfb318e1 (diff)
downloadleetcode-a950959b8a433478ab7a33b34fb1f4d2d7bafcb8.tar.gz
leetcode-a950959b8a433478ab7a33b34fb1f4d2d7bafcb8.zip
3373. maximise the number of target nodes after connecting trees 2
-rw-r--r--maximise_num_target_node_tree2.c139
-rw-r--r--maximise_num_target_node_tree2.py63
2 files changed, 202 insertions, 0 deletions
diff --git a/maximise_num_target_node_tree2.c b/maximise_num_target_node_tree2.c
new file mode 100644
index 0000000..f00d00e
--- /dev/null
+++ b/maximise_num_target_node_tree2.c
@@ -0,0 +1,139 @@
+// 3373. Maximize the Number of Target Nodes After Connecting Trees II
+#include "leetcode.h"
+
+/*
+ * there exists two undirect trees with 'n' and 'm' nodes, labeled from '[0, n -
+ * 1]' andc '[0, m - 1]' respectively. you are given two 2d integer arrays
+ * 'edges1' and 'edges2' of lengths 'n - 1' and 'm - 1' respectively. node 'u'
+ * is target to node 'v' if the number of edges on the path from 'u' to 'v' is
+ * even. note that a node is always target to itself. return an array of
+ * integers where 'ans[i]' is the maximum possible number of nodes that are
+ * target to node 'i' of the first tree if you had to connect one node from the
+ * first tree to another node in the second tree. note that queries are
+ * independent from each other. that is, for every query, you will remove the
+ * added edge before proceeding to the next query.
+ */
+
+int *maxTargetNodes(int **edges1, int edges1Size, int *edges1ColSize,
+ int **edges2, int edges2Size, int *edges2ColSize,
+ int *returnSize) {
+ int n = edges1Size + 1, m = edges2Size + 1;
+ *returnSize = n;
+ int *ans = (int *)malloc(n * sizeof(int));
+ int *g1deg = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < edges1Size; i++) {
+ int u = edges1[i][0], v = edges1[i][1];
+ g1deg[u]++;
+ g1deg[v]++;
+ }
+ int **g1adj = (int **)malloc(n * sizeof(int *));
+ for (int i = 0; i < n; i++)
+ g1adj[i] = (int *)malloc(g1deg[i] * sizeof(int));
+ int *tmpd1 = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < edges1Size; i++) {
+ int u = edges1[i][0], v = edges1[i][1];
+ g1adj[u][tmpd1[u]++] = v;
+ g1adj[v][tmpd1[v]++] = u;
+ }
+ free(tmpd1);
+ int *c1 = (int *)malloc(n * sizeof(int));
+ for (int i = 0; i < n; i++)
+ c1[i] = -1;
+ int *q1 = (int *)malloc(n * sizeof(int));
+ int front1 = 0, rear1 = 0, cnt10 = 0, cnt11 = 0;
+ c1[0] = 0;
+ cnt10++;
+ q1[rear1++] = 0;
+ while (front1 < rear1) {
+ int u = q1[front1++];
+ for (int i = 0; i < g1deg[u]; i++) {
+ int v = g1adj[u][i];
+ if (c1[v] == -1) {
+ c1[v] = c1[u] ^ 1;
+ if (!c1[v])
+ cnt10++;
+ else
+ cnt11++;
+ q1[rear1++] = v;
+ }
+ }
+ }
+ for (int i = 0; i < n; i++)
+ free(g1adj[i]);
+ free(g1adj);
+ free(g1deg);
+ free(q1);
+
+ int *g2deg = (int *)calloc(m, sizeof(int));
+ for (int i = 0; i < edges2Size; i++) {
+ int u = edges2[i][0], v = edges2[i][1];
+ g2deg[u]++;
+ g2deg[v]++;
+ }
+ int **g2adj = (int **)malloc(m * sizeof(int *));
+ for (int i = 0; i < m; i++)
+ g2adj[i] = (int *)malloc(g2deg[i] * sizeof(int));
+ int *tmpd2 = (int *)calloc(m, sizeof(int));
+ for (int i = 0; i < edges2Size; i++) {
+ int u = edges2[i][0], v = edges2[i][1];
+ g2adj[u][tmpd2[u]++] = v;
+ g2adj[v][tmpd2[v]++] = u;
+ }
+ free(tmpd2);
+ int *v2 = (int *)malloc(m * sizeof(int));
+ for (int i = 0; i < m; i++)
+ v2[i] = -1;
+ int *q2 = (int *)malloc(m * sizeof(int));
+ int front2 = 0, rear2 = 0, cnt20 = 0, cnt21 = 0;
+ v2[0] = 0;
+ cnt20++;
+ q2[rear2++] = 0;
+ while (front2 < rear2) {
+ int u = q2[front2++];
+ for (int i = 0; i < g2deg[u]; i++) {
+ int v = g2adj[u][i];
+ if (v2[v] == -1) {
+ v2[v] = v2[u] ^ 1;
+ if (!v2[v])
+ cnt20++;
+ else
+ cnt21++;
+ q2[rear2++] = v;
+ }
+ }
+ }
+ int m2 = cnt20 > cnt21 ? cnt20 : cnt21;
+ for (int i = 0; i < n; i++)
+ ans[i] = (!c1[i] ? cnt10 : cnt11) + m2;
+ free(c1);
+ return ans;
+}
+
+int main() {
+ int e11i[4][2] = {{0, 1}, {0, 2}, {2, 3}, {2, 4}},
+ e21i[7][2] = {{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}},
+ rs1;
+ int e12i[4][2] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}},
+ e22i[3][2] = {{0, 1}, {1, 2}, {2, 3}}, rs2;
+ struct two_d_arr e11, e21, e12, e22;
+ two_d_arr_init(&e11, ARRAY_SIZE(e11i), ARRAY_SIZE(e11i[0]), e11i);
+ two_d_arr_init(&e21, ARRAY_SIZE(e21i), ARRAY_SIZE(e21i[0]), e21i);
+ two_d_arr_init(&e12, ARRAY_SIZE(e12i), ARRAY_SIZE(e12i[0]), e12i);
+ two_d_arr_init(&e22, ARRAY_SIZE(e22i), ARRAY_SIZE(e22i[0]), e22i);
+ int *mtn1 = maxTargetNodes(e11.arr, e11.row_size, e11.col_size, e21.arr,
+ e21.row_size, e21.col_size, &rs1);
+ int *mtn2 = maxTargetNodes(e12.arr, e12.row_size, e12.col_size, e22.arr,
+ e22.row_size, e22.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", mtn1[i]); // expect: 8 7 7 8 8
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", mtn2[i]); // expect: 3 6 6 6 6
+ printf("\n");
+ free(mtn1);
+ free(mtn2);
+ two_d_arr_free(&e11);
+ two_d_arr_free(&e21);
+ two_d_arr_free(&e12);
+ two_d_arr_free(&e22);
+}
diff --git a/maximise_num_target_node_tree2.py b/maximise_num_target_node_tree2.py
new file mode 100644
index 0000000..264c1ea
--- /dev/null
+++ b/maximise_num_target_node_tree2.py
@@ -0,0 +1,63 @@
+# 3373. Maximize the Number of Target Nodes After Connecting Trees II
+from collections import deque
+
+"""
+there exists two undirect trees with 'n' and 'm' nodes, labeled from '[0, n -
+1]' andc '[0, m - 1]' respectively. you are given two 2d integer arrays
+'edges1' and 'edges2' of lengths 'n - 1' and 'm - 1' respectively. node 'u'
+is target to node 'v' if the number of edges on the path from 'u' to 'v' is
+even. note that a node is always target to itself. return an array of
+integers where 'ans[i]' is the maximum possible number of nodes that are
+target to node 'i' of the first tree if you had to connect one node from the
+first tree to another node in the second tree. note that queries are
+independent from each other. that is, for every query, you will remove the
+added edge before proceeding to the next query.
+"""
+
+
+class Solution(object):
+ def maxTargetNodes(self, edges1, edges2):
+ """
+ :type edges1: List[List[int]]
+ :type edges2: List[List[int]]
+ :rtype: List[int]
+ """
+
+ def find_even(edges, n):
+ graph = [[] for _ in range(n)]
+ queue = deque([(0, -1, True)])
+ evens = [False] * n
+
+ for u, v in edges:
+ graph[u].append(v)
+ graph[v].append(u)
+
+ while queue:
+ node, parent, curr = queue.popleft()
+ evens[node] = curr
+ for child in graph[node]:
+ if child == parent:
+ continue
+ queue.append((child, node, not curr))
+ return evens
+
+ n, m = len(edges1) + 1, len(edges2) + 1
+ e1, e2 = find_even(edges1, n), find_even(edges2, m)
+ s1, s2 = sum(e1), sum(e2)
+ x = max(s2, m - s2)
+ return [x + (s1 if even else n - s1) for even in e1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxTargetNodes(
+ edges1=[[0, 1], [0, 2], [2, 3], [2, 4]],
+ edges2=[[0, 1], [0, 2], [0, 3], [2, 7], [1, 4], [4, 5], [4, 6]],
+ )
+ )
+ print(
+ obj.maxTargetNodes(
+ edges1=[[0, 1], [0, 2], [0, 3], [0, 4]], edges2=[[0, 1], [1, 2], [2, 3]]
+ )
+ )