aboutsummaryrefslogtreecommitdiff
path: root/longest_path_diff_adjacent_char.c
blob: e77ae15fcf52e185a0f33837ed2b5341e77183dc (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
// 2246. Longest Path With Different Adjacent Characters
#include "leetcode.h"

/*
 * you are given a tree (ie. a connected undirected graph that has no cycles)
 * rooted at node '0' consisting of 'n' nodes numbered from '0' to 'n - 1'. the
 * tree is represented by a 0-indexed array 'parent' of size 'n' where
 * 'parent[i]' is the parent of node 'i'. since node 0 is the root, 'parent[0] =
 * -1'. you are also given a string 's' of length 'n', where 's[i]' is the
 * character assigned to node 'i'. return the legnth of the longest path in the
 * tree such that no pair of adjacnet nodes on the path have the same character
 * assigned to them.
 */

struct node {
  bool visited;
  int children;
  int *adjacent_list;
};

void dfs(int curr_node, int *dist, struct node **root, int parent_size, char *s,
         int *res) {
  int curr_child;
  dist[curr_node] = 1;
  root[curr_node]->visited = true;
  for (int i = 0; i < root[curr_node]->children; i++) {
    curr_child = root[curr_node]->adjacent_list[i];
    if (!root[curr_child]->visited) {
      dfs(curr_child, dist, root, parent_size, s, res);
      if (s[curr_node] != s[curr_child]) {
        *res = fmax(*res, dist[curr_node] + dist[curr_child]);
        dist[curr_node] = fmax(dist[curr_node], dist[curr_child] + 1);
      }
    }
  }
}

int longestPath(int *parent, int parentSize, char *s) {
  int ans = 1;
  int *cnt = (int *)calloc(parentSize, sizeof(int));
  int *dist = (int *)calloc(parentSize, sizeof(int));
  struct node **root =
      (struct node **)malloc(parentSize * sizeof(struct node *));
  struct node *curr_node;
  for (int i = 1; i < parentSize; i++) {
    cnt[parent[i]]++;
    cnt[i]++;
  }
  for (int i = 0; i < parentSize; i++) {
    root[i] = (struct node *)malloc(sizeof(struct node));
    root[i]->visited = false;
    root[i]->children = 0;
    root[i]->adjacent_list = (int *)malloc(cnt[i] * sizeof(int));
  }
  for (int i = 1; i < parentSize; i++) {
    curr_node = root[parent[i]];
    curr_node->adjacent_list[curr_node->children] = i;
    curr_node->children++;
  }
  dfs(0, dist, root, parentSize, s, &ans);
  for (int i = 0; i < parentSize; i++) {
    free(root[i]->adjacent_list);
    free(root[i]);
  }
  free(cnt), free(dist), free(root);
  return ans;
}

int main() {
  int p1[] = {-1, 0, 0, 1, 1, 2}, p2[] = {-1, 0, 0, 0};
  char *s1 = "abacbe", *s2 = "aabc";
  printf("%d\n", longestPath(p1, ARRAY_SIZE(p1), s1)); // expect: 3
  printf("%d\n", longestPath(p2, ARRAY_SIZE(p2), s2)); // expect: 3
}