aboutsummaryrefslogtreecommitdiff
path: root/largest_colour_val_dir_graph.c
blob: 79771bfff109511b46ba9977d90ca590ef69d3dd (plain)
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
}