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
|
// 2359. Find Closest Node to Given Two Nodes
#include "leetcode.h"
/*
* you are given a directed graph of 'n' nodes numbered from 0 to 'n - 1', where
* each node has at most one outgoing edge. the graph is represented with a
* given 0-indexed array 'edges' of size 'n', indicating that there is a
* directed edge from node 'i' to node 'edges[i]'. if there is no outgoing edge
* from 'i' then 'edges[i] == -1'. you are also given two integers 'node1' and
* 'node2'. return the indes of the node that can be reached from both 'node1'
* and 'node2' such that the maximum between the distance from 'node1' to that
* node and from 'node2' to that node is minimised
*/
void dfs(int node, int dist, int *edge, int *n) {
while (node != -1 && n[node] == -1) {
n[node] = dist++;
node = edge[node];
}
}
int closestMeetingNode(int *edges, int edgesSize, int node1, int node2) {
int ans = -1, dist = INT_MAX;
int *n1 = (int *)malloc(edgesSize * sizeof(int));
int *n2 = (int *)malloc(edgesSize * sizeof(int));
for (int i = 0; i < edgesSize; i++) {
n1[i] = -1;
n2[i] = -1;
}
dfs(node1, 0, edges, n1);
dfs(node2, 0, edges, n2);
for (int i = 0; i < edgesSize; ++i)
if (fmin(n1[i], n2[i]) >= 0 && fmax(n1[i], n2[i]) < dist) {
dist = fmax(n1[i], n2[i]);
ans = i;
}
free(n1);
free(n2);
return ans;
}
int main() {
int e1[] = {2, 2, 3, -1}, e2[] = {1, 2, -1};
printf("%d\n", closestMeetingNode(e1, ARRAY_SIZE(e1), 0, 1)); // expect: 2
printf("%d\n", closestMeetingNode(e2, ARRAY_SIZE(e2), 0, 2)); // expect: 2
}
|