diff options
Diffstat (limited to 'closest_node_2_nodes.py')
-rw-r--r-- | closest_node_2_nodes.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/closest_node_2_nodes.py b/closest_node_2_nodes.py new file mode 100644 index 0000000..a271f84 --- /dev/null +++ b/closest_node_2_nodes.py @@ -0,0 +1,46 @@ +# 2359. Find Closest Node to Given Two Nodes + +""" +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 +""" + + +class Solution(object): + def dfs(self, node, edges, dist, vis): + vis[node] = True + neigh = edges[node] + if neigh != -1 and vis[neigh] == False: + dist[neigh] = dist[node] + 1 + self.dfs(neigh, edges, dist, vis) + + def closestMeetingNode(self, edges, node1, node2): + """ + :type edges: List[int] + :type node1: int + :type node2: int + :rtype: int + """ + n, ans = len(edges), -1 + min_dist = float("inf") + n1, n2 = [0] * n, [0] * n + v1, v2 = [False] * n, [False] * n + self.dfs(node1, edges, n1, v1) + self.dfs(node2, edges, n2, v2) + for i in range(n): + if v1[i] and v2[i] and min_dist > max(n1[i], n2[i]): + min_dist = max(n1[i], n2[i]) + ans = i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.closestMeetingNode(edges=[2, 2, 3, -1], node1=0, node2=1)) + print(obj.closestMeetingNode(edges=[1, 2, -1], node1=0, node2=2)) |