aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-25 19:39:19 -0600
committerJack Sangdahl <[email protected]>2025-05-25 19:39:19 -0600
commit0f8510ead88cab82038d1ab8cba3997a508370eb (patch)
treefb22e99703787370be48502dcf8db1a6a21ca409
parentf1299c65b0a2d50a27cea1977fb85628684789f7 (diff)
downloadleetcode-0f8510ead88cab82038d1ab8cba3997a508370eb.tar.gz
leetcode-0f8510ead88cab82038d1ab8cba3997a508370eb.zip
1857. largest colour value in directed graph
-rw-r--r--largest_colour_val_dir_graph.c115
-rw-r--r--largest_colour_val_dir_graph.py57
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]]))