diff options
author | Jack Sangdahl <[email protected]> | 2025-05-25 19:39:19 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-25 19:39:19 -0600 |
commit | 0f8510ead88cab82038d1ab8cba3997a508370eb (patch) | |
tree | fb22e99703787370be48502dcf8db1a6a21ca409 | |
parent | f1299c65b0a2d50a27cea1977fb85628684789f7 (diff) | |
download | leetcode-0f8510ead88cab82038d1ab8cba3997a508370eb.tar.gz leetcode-0f8510ead88cab82038d1ab8cba3997a508370eb.zip |
1857. largest colour value in directed graph
-rw-r--r-- | largest_colour_val_dir_graph.c | 115 | ||||
-rw-r--r-- | largest_colour_val_dir_graph.py | 57 |
2 files changed, 172 insertions, 0 deletions
diff --git a/largest_colour_val_dir_graph.c b/largest_colour_val_dir_graph.c new file mode 100644 index 0000000..79771bf --- /dev/null +++ b/largest_colour_val_dir_graph.c @@ -0,0 +1,115 @@ +// 1857. Largest Color Value in a Directed Graph +#include "leetcode.h" + +/* + * there is a directed graph of 'n' coloured nodes and 'm' edges. the nodes are + * numbered from 0 to 'n - 1'. you are given a tring 'colours' where + * 'colours[i]' is a lowercase english letter representing the colour of the + * i'th node in this graph (0-indexed). you are also given a 2d integer array + * 'edges' where 'edges[i] = [ai, bi]' indicates that there is a directed edge + * from node 'ai' to 'bi'. a valid path in the graph is a sequence of nodes such + * that there is a directed edge for every ' 1 <= i < k'. the collour value of + * the path is the number of nodes that coloured the most frequently occuring + * along the path. return the largest colour value of any valid path in the + * given graph, or -1 if the graph contains a cycle. + */ + +struct node { + int val; + struct node *next; +}; + +struct graph { + struct node *next; + char colour; + int *cnt; +}; + +struct node *graph_create(struct node *prev, int val) { + struct node *obj = (struct node *)malloc(sizeof(struct node)); + obj->next = prev; + obj->val = val; + return obj; +} + +void graph_free(struct graph *s, int n) { + for (int i = 0; i < n; i++) { + while (s[i].next) { + struct node *tmp = s[i].next; + s[i].next = s[i].next->next; + free(tmp); + } + free(s[i].cnt); + } + free(s); +} + +void search(int val, struct graph *plan, bool *vis, bool *cycle, int *res) { + vis[val] = true; + while (plan[val].next) { + int new = plan[val].next->val; + if (vis[new]) { + *cycle = true; + return; + } + if (plan[new].cnt) { + for (int i = 0; i < 26; i++) + if (plan[val].cnt[i] < plan[new].cnt[i]) + plan[val].cnt[i] = plan[new].cnt[i]; + plan[val].next = plan[val].next->next; + continue; + } + plan[new].cnt = (int *)calloc(26, sizeof(int)); + search(new, plan, vis, cycle, res); + for (int i = 0; i < 26; i++) + if (plan[val].cnt[i] < plan[new].cnt[i]) + plan[val].cnt[i] = plan[new].cnt[i]; + plan[val].next = plan[val].next->next; + } + plan[val].cnt[plan[val].colour - 'a']++; + if (*res < plan[val].cnt[plan[val].colour - 'a']) + *res = plan[val].cnt[plan[val].colour - 'a']; + vis[val] = false; +} + +int largestPathValue(char *colors, int **edges, int edgesSize, + int *edgesColSize) { + int n = strlen(colors); + struct graph *plan = (struct graph *)calloc(n, sizeof(struct graph)); + bool *vis = (bool *)calloc(n, sizeof(bool)); + for (int i = 0; i < n; i++) + plan[i].colour = colors[i]; + for (int i = 0; i < edgesSize; i++) { + if (edges[i][0] == edges[i][1]) { + graph_free(plan, n); + return -1; + } + plan[edges[i][0]].next = graph_create(plan[edges[i][0]].next, edges[i][1]); + } + bool cycle = false; + int ans = 0; + for (int i = 0; i < n; i++) { + if (!plan[i].cnt) { + plan[i].cnt = (int *)calloc(26, sizeof(int)); + search(i, plan, vis, &cycle, &ans); + if (cycle) { + graph_free(plan, n); + return -1; + } + } + } + graph_free(plan, n); + return ans; +} + +int main() { + char *c1 = "abaca", *c2 = "a"; + int e1i[4][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}}, e2i[1][2] = {{0, 0}}; + struct two_d_arr e1, e2; + two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i); + two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i); + printf("%d\n", + largestPathValue(c1, e1.arr, e1.row_size, e1.col_size)); // expect: 3 + printf("%d\n", + largestPathValue(c2, e2.arr, e2.row_size, e2.col_size)); // expect: -1 +} diff --git a/largest_colour_val_dir_graph.py b/largest_colour_val_dir_graph.py new file mode 100644 index 0000000..170c1a5 --- /dev/null +++ b/largest_colour_val_dir_graph.py @@ -0,0 +1,57 @@ +# 1857. Largest Color Value in a Directed Graph +from collections import deque + +""" +there is a directed graph of 'n' coloured nodes and 'm' edges. the nodes are +numbered from 0 to 'n - 1'. you are given a tring 'colours' where +'colours[i]' is a lowercase english letter representing the colour of the +i'th node in this graph (0-indexed). you are also given a 2d integer array +'edges' where 'edges[i] = [ai, bi]' indicates that there is a directed edge +from node 'ai' to 'bi'. a valid path in the graph is a sequence of nodes such +that there is a directed edge for every ' 1 <= i < k'. the collour value of +the path is the number of nodes that coloured the most frequently occuring +along the path. return the largest colour value of any valid path in the +given graph, or -1 if the graph contains a cycle. +""" + + +class Solution(object): + def largestPathValue(self, colors, edges): + """ + :type colors: str + :type edges: List[List[int]] + :rtype: int + """ + n = len(colors) + indeg = [0] * n + graph = [[] for _ in range(n)] + for i in edges: + graph[i[0]].append(i[1]) + indeg[i[1]] += 1 + zero_indeg = deque() + for i in range(n): + if indeg[i] == 0: + zero_indeg.append(i) + cnt = [[0] * 26 for _ in range(n)] + for i in range(n): + cnt[i][ord(colors[i]) - ord("a")] += 1 + max_cnt, vis = 0, 0 + while zero_indeg: + u = zero_indeg.popleft() + vis += 1 + for v in graph[u]: + for i in range(26): + cnt[v][i] = max( + cnt[v][i], cnt[u][i] + (ord(colors[v]) - ord("a") == i) + ) + indeg[v] -= 1 + if indeg[v] == 0: + zero_indeg.append(v) + max_cnt = max(max_cnt, max(cnt[u])) + return max_cnt if vis == n else -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.largestPathValue(colors="abaca", edges=[[0, 1], [0, 2], [2, 3], [3, 4]])) + print(obj.largestPathValue(colors="a", edges=[[0, 0]])) |