aboutsummaryrefslogtreecommitdiff
path: root/closest_node_2_nodes.c
blob: 444505cbf14010da10c1747a159fc6ba6ed39183 (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
// 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
}