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
}
|