diff options
author | Jack Sangdahl <[email protected]> | 2025-01-12 20:18:50 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-13 20:19:28 -0700 |
commit | b4e04c3e1da4d6ab0b439b71622a32d61fb25c9d (patch) | |
tree | 8cd96768cff97cb6de23e655b68803c520e6f9e1 | |
parent | b7b7dd2713396b261a1ffd8be1c330c2fd828f9d (diff) | |
download | leetcode-b4e04c3e1da4d6ab0b439b71622a32d61fb25c9d.tar.gz leetcode-b4e04c3e1da4d6ab0b439b71622a32d61fb25c9d.zip |
2581. count number of possible root nodes
-rw-r--r-- | count_number_root_nodes.c | 104 | ||||
-rw-r--r-- | count_number_root_nodes.py | 66 |
2 files changed, 170 insertions, 0 deletions
diff --git a/count_number_root_nodes.c b/count_number_root_nodes.c new file mode 100644 index 0000000..ba684ea --- /dev/null +++ b/count_number_root_nodes.c @@ -0,0 +1,104 @@ +// 2581. Count Number of Possible Root Nodes +#include "leetcode.h" + +bool check(int *nums, int nums_size, int k) { + for (int i = 0; i < nums_size; i++) + if (nums[i] == k) + return true; + return false; +} + +void dfs(int **next, int *next_count, int **guess, int *guess_count, int from, + int curr, int *correct) { + for (int i = 0; i < next_count[curr]; i++) { + if (next[curr][i] == from) { + i++; + while (i < next_count[curr]) { + if (check(guess[curr], guess_count[curr], next[curr][i])) { + *correct += 1; + } + dfs(next, next_count, guess, guess_count, curr, next[curr][i], correct); + i++; + } + } else { + if (check(guess[curr], guess_count[curr], next[curr][i])) { + *correct += 1; + } + dfs(next, next_count, guess, guess_count, curr, next[curr][i], correct); + } + } +} + +void change_root(int **next, int *next_count, int **guess, int *guess_count, + int from, int curr, int correct, int *ans) { + for (int i = 0; i < next_count[curr]; i++) { + if (next[curr][i] == from) + continue; + int count = correct; + if (check(guess[curr], guess_count[curr], next[curr][i])) + count--; + if (check(guess[next[curr][i]], guess_count[next[curr][i]], curr)) + count++; + if (count >= 0) + (*ans)++; + change_root(next, next_count, guess, guess_count, curr, next[curr][i], + count, ans); + } +} + +int rootCount(int **edges, int edgesSize, int *edgesColSize, int **guesses, + int guessesSize, int *guessesColSize, int k) { + int m = edgesSize + 1, correct = 0, ans = 0; + int **next = (int **)malloc(m * sizeof(int *)); + int *next_count = (int *)calloc(m, sizeof(int)); + int **guess = (int **)malloc(m * sizeof(int *)); + int *guess_count = (int *)calloc(m, sizeof(int)); + for (int i = 0; i < m; i++) { + next[i] = malloc(sizeof(int) * 20); + guess[i] = malloc(sizeof(int) * 20); + } + for (int i = 0; i < edgesSize; i++) { + next[edges[i][0]][next_count[edges[i][0]]] = edges[i][1]; + next_count[edges[i][0]]++; + next[edges[i][1]][next_count[edges[i][1]]] = edges[i][0]; + next_count[edges[i][1]]++; + } + for (int i = 0; i < guessesSize; i++) { + guess[guesses[i][0]][guess_count[guesses[i][0]]] = guesses[i][1]; + guess_count[guesses[i][0]]++; + } + for (int i = 0; i < next_count[0]; i++) { + if (check(guess[0], guess_count[0], next[0][i])) + correct++; + dfs(next, next_count, guess, guess_count, 0, next[0][i], &correct); + } + correct -= k; + if (correct >= 0) + ans++; + change_root(next, next_count, guess, guess_count, -1, 0, correct, &ans); + free(next_count), free(guess_count); + for (int i = 0; i < m; i++) + free(next[i]), free(guess[i]); + free(next), free(guess); + return ans; +} + +int main() { + int e1i[4][2] = {{0, 1}, {1, 2}, {1, 3}, {4, 2}}, + g1i[4][2] = {{1, 3}, {0, 1}, {1, 0}, {2, 4}}; + int e2i[4][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}}, + g2i[4][2] = {{1, 0}, {3, 4}, {2, 1}, {3, 2}}; + struct two_d_arr e1, g1, e2, g2; + two_d_arr_init(&e1, 4, 2, e1i); + two_d_arr_init(&g1, 4, 2, g1i); + two_d_arr_init(&e2, 4, 2, e2i); + two_d_arr_init(&g2, 4, 2, g2i); + printf("%d\n", rootCount(e1.arr, e1.row_size, e1.col_size, g1.arr, + g1.row_size, g1.col_size, 3)); // expect: 3 + printf("%d\n", rootCount(e2.arr, e2.row_size, e2.col_size, g2.arr, + g2.row_size, g2.col_size, 1)); // expect: 5 + two_d_arr_free(&e1); + two_d_arr_free(&g1); + two_d_arr_free(&e2); + two_d_arr_free(&g2); +} diff --git a/count_number_root_nodes.py b/count_number_root_nodes.py new file mode 100644 index 0000000..ddd4982 --- /dev/null +++ b/count_number_root_nodes.py @@ -0,0 +1,66 @@ +# 2581. Count Number of Possible Root Nodes +from collections import defaultdict + + +class Solution(object): + def rootCount(self, edges, guesses, k): + """ + :type edges: List[List[int]] + :type guesses: List[List[int]] + :type k: int + :rtype: int + """ + adj = defaultdict(set) + for u, v in edges: + adj[u].add(v) + adj[v].add(u) + child = defaultdict(set) + for u, v in guesses: + child[u].add(v) + parents, total_guess = {}, 0 + + def fill_parent(node, par): + nonlocal total_guess + parents[node] = par + for i in adj[node]: + if i != par: + if i in child[node]: + total_guess += 1 + fill_parent(i, node) + + fill_parent(0, -1) + res = 0 + + def dfs(node, par, correct_guess): + nonlocal res + cur = correct_guess + if node in child[par]: + cur -= 1 + if par in child[node]: + cur += 1 + if cur >= k: + res += 1 + for i in adj[node]: + if i != par: + dfs(i, node, cur) + + dfs(0, -1, total_guess) + return res + + +if __name__ == "__main__": + obj = Solution() + print( + obj.rootCount( + edges=[[0, 1], [1, 2], [1, 3], [4, 2]], + guesses=[[1, 3], [0, 1], [1, 0], [2, 4]], + k=3, + ) + ) + print( + obj.rootCount( + edges=[[0, 1], [1, 2], [2, 3], [3, 4]], + guesses=[[1, 0], [3, 4], [2, 1], [3, 2]], + k=1, + ) + ) |