1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
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
}
|