Depth-First Search
Graph
Description
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 index 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 minimized . If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1
.
Note that edges
may contain cycles.
Example 1:
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1
Output: 2
Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1.
The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.
Example 2:
Input: edges = [1,2,-1], node1 = 0, node2 = 2
Output: 2
Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0.
The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.
Constraints:
n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 class Solution :
def closestMeetingNode ( self , edges : List [ int ], node1 : int , node2 : int ) -> int :
def dijkstra ( i ):
dist = [ inf ] * n
dist [ i ] = 0
q = [( 0 , i )]
while q :
i = heappop ( q )[ 1 ]
for j in g [ i ]:
if dist [ j ] > dist [ i ] + 1 :
dist [ j ] = dist [ i ] + 1
heappush ( q , ( dist [ j ], j ))
return dist
g = defaultdict ( list )
for i , j in enumerate ( edges ):
if j != - 1 :
g [ i ] . append ( j )
n = len ( edges )
d1 = dijkstra ( node1 )
d2 = dijkstra ( node2 )
ans , d = - 1 , inf
for i , ( a , b ) in enumerate ( zip ( d1 , d2 )):
if ( t := max ( a , b )) < d :
d = t
ans = i
return ans
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 class Solution {
private int n ;
private List < Integer >[] g ;
public int closestMeetingNode ( int [] edges , int node1 , int node2 ) {
n = edges . length ;
g = new List [ n ] ;
Arrays . setAll ( g , k -> new ArrayList <> ());
for ( int i = 0 ; i < n ; ++ i ) {
if ( edges [ i ] != - 1 ) {
g [ i ] . add ( edges [ i ] );
}
}
int [] d1 = dijkstra ( node1 );
int [] d2 = dijkstra ( node2 );
int d = 1 << 30 ;
int ans = - 1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int t = Math . max ( d1 [ i ] , d2 [ i ] );
if ( t < d ) {
d = t ;
ans = i ;
}
}
return ans ;
}
private int [] dijkstra ( int i ) {
int [] dist = new int [ n ] ;
Arrays . fill ( dist , 1 << 30 );
dist [ i ] = 0 ;
PriorityQueue < int []> q = new PriorityQueue <> (( a , b ) -> a [ 0 ] - b [ 0 ] );
q . offer ( new int [] { 0 , i });
while ( ! q . isEmpty ()) {
var p = q . poll ();
i = p [ 1 ] ;
for ( int j : g [ i ] ) {
if ( dist [ j ] > dist [ i ] + 1 ) {
dist [ j ] = dist [ i ] + 1 ;
q . offer ( new int [] { dist [ j ] , j });
}
}
}
return dist ;
}
}
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 class Solution {
public :
int closestMeetingNode ( vector < int >& edges , int node1 , int node2 ) {
int n = edges . size ();
vector < vector < int >> g ( n );
for ( int i = 0 ; i < n ; ++ i ) {
if ( edges [ i ] != -1 ) {
g [ i ]. push_back ( edges [ i ]);
}
}
const int inf = 1 << 30 ;
using pii = pair < int , int > ;
auto dijkstra = [ & ]( int i ) {
vector < int > dist ( n , inf );
dist [ i ] = 0 ;
priority_queue < pii , vector < pii > , greater < pii >> q ;
q . emplace ( 0 , i );
while ( ! q . empty ()) {
auto p = q . top ();
q . pop ();
i = p . second ;
for ( int j : g [ i ]) {
if ( dist [ j ] > dist [ i ] + 1 ) {
dist [ j ] = dist [ i ] + 1 ;
q . emplace ( dist [ j ], j );
}
}
}
return dist ;
};
vector < int > d1 = dijkstra ( node1 );
vector < int > d2 = dijkstra ( node2 );
int ans = -1 , d = inf ;
for ( int i = 0 ; i < n ; ++ i ) {
int t = max ( d1 [ i ], d2 [ i ]);
if ( t < d ) {
d = t ;
ans = i ;
}
}
return ans ;
}
};
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 func closestMeetingNode ( edges [] int , node1 int , node2 int ) int {
n := len ( edges )
g := make ([][] int , n )
for i , j := range edges {
if j != - 1 {
g [ i ] = append ( g [ i ], j )
}
}
const inf int = 1 << 30
dijkstra := func ( i int ) [] int {
dist := make ([] int , n )
for j := range dist {
dist [ j ] = inf
}
dist [ i ] = 0
q := hp {}
heap . Push ( & q , pair { 0 , i })
for len ( q ) > 0 {
i := heap . Pop ( & q ).( pair ). i
for _ , j := range g [ i ] {
if dist [ j ] > dist [ i ] + 1 {
dist [ j ] = dist [ i ] + 1
heap . Push ( & q , pair { dist [ j ], j })
}
}
}
return dist
}
d1 := dijkstra ( node1 )
d2 := dijkstra ( node2 )
ans , d := - 1 , inf
for i , a := range d1 {
b := d2 [ i ]
t := max ( a , b )
if t < d {
d = t
ans = i
}
}
return ans
}
type pair struct { d , i int }
type hp [] pair
func ( h hp ) Len () int { return len ( h ) }
func ( h hp ) Less ( i , j int ) bool { return h [ i ]. d < h [ j ]. d }
func ( h hp ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * hp ) Push ( v any ) { * h = append ( * h , v .( pair )) }
func ( h * hp ) Pop () any { a := * h ; v := a [ len ( a ) - 1 ]; * h = a [: len ( a ) - 1 ]; return v }
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 function closestMeetingNode ( edges : number [], node1 : number , node2 : number ) : number {
const n = edges . length ;
const g = Array . from ({ length : n }, () => []);
for ( let i = 0 ; i < n ; ++ i ) {
if ( edges [ i ] != - 1 ) {
g [ i ]. push ( edges [ i ]);
}
}
const inf = 1 << 30 ;
const f = ( i : number ) => {
const dist = new Array ( n ). fill ( inf );
dist [ i ] = 0 ;
const q : number [] = [ i ];
while ( q . length ) {
i = q . shift ();
for ( const j of g [ i ]) {
if ( dist [ j ] == inf ) {
dist [ j ] = dist [ i ] + 1 ;
q . push ( j );
}
}
}
return dist ;
};
const d1 = f ( node1 );
const d2 = f ( node2 );
let ans = - 1 ;
let d = inf ;
for ( let i = 0 ; i < n ; ++ i ) {
const t = Math . max ( d1 [ i ], d2 [ i ]);
if ( t < d ) {
d = t ;
ans = i ;
}
}
return ans ;
}
Solution 2
Python3 Java C++ Go
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 class Solution :
def closestMeetingNode ( self , edges : List [ int ], node1 : int , node2 : int ) -> int :
def f ( i ):
dist = [ inf ] * n
dist [ i ] = 0
q = deque ([ i ])
while q :
i = q . popleft ()
for j in g [ i ]:
if dist [ j ] == inf :
dist [ j ] = dist [ i ] + 1
q . append ( j )
return dist
g = defaultdict ( list )
for i , j in enumerate ( edges ):
if j != - 1 :
g [ i ] . append ( j )
n = len ( edges )
d1 = f ( node1 )
d2 = f ( node2 )
ans , d = - 1 , inf
for i , ( a , b ) in enumerate ( zip ( d1 , d2 )):
if ( t := max ( a , b )) < d :
d = t
ans = i
return ans
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 class Solution {
private int n ;
private List < Integer >[] g ;
public int closestMeetingNode ( int [] edges , int node1 , int node2 ) {
n = edges . length ;
g = new List [ n ] ;
Arrays . setAll ( g , k -> new ArrayList <> ());
for ( int i = 0 ; i < n ; ++ i ) {
if ( edges [ i ] != - 1 ) {
g [ i ] . add ( edges [ i ] );
}
}
int [] d1 = f ( node1 );
int [] d2 = f ( node2 );
int d = 1 << 30 ;
int ans = - 1 ;
for ( int i = 0 ; i < n ; ++ i ) {
int t = Math . max ( d1 [ i ] , d2 [ i ] );
if ( t < d ) {
d = t ;
ans = i ;
}
}
return ans ;
}
private int [] f ( int i ) {
int [] dist = new int [ n ] ;
Arrays . fill ( dist , 1 << 30 );
dist [ i ] = 0 ;
Deque < Integer > q = new ArrayDeque <> ();
q . offer ( i );
while ( ! q . isEmpty ()) {
i = q . poll ();
for ( int j : g [ i ] ) {
if ( dist [ j ] == 1 << 30 ) {
dist [ j ] = dist [ i ] + 1 ;
q . offer ( j );
}
}
}
return dist ;
}
}
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 class Solution {
public :
int closestMeetingNode ( vector < int >& edges , int node1 , int node2 ) {
int n = edges . size ();
vector < vector < int >> g ( n );
for ( int i = 0 ; i < n ; ++ i ) {
if ( edges [ i ] != -1 ) {
g [ i ]. push_back ( edges [ i ]);
}
}
const int inf = 1 << 30 ;
using pii = pair < int , int > ;
auto f = [ & ]( int i ) {
vector < int > dist ( n , inf );
dist [ i ] = 0 ;
queue < int > q {{ i }};
while ( ! q . empty ()) {
i = q . front ();
q . pop ();
for ( int j : g [ i ]) {
if ( dist [ j ] == inf ) {
dist [ j ] = dist [ i ] + 1 ;
q . push ( j );
}
}
}
return dist ;
};
vector < int > d1 = f ( node1 );
vector < int > d2 = f ( node2 );
int ans = -1 , d = inf ;
for ( int i = 0 ; i < n ; ++ i ) {
int t = max ( d1 [ i ], d2 [ i ]);
if ( t < d ) {
d = t ;
ans = i ;
}
}
return ans ;
}
};
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 func closestMeetingNode ( edges [] int , node1 int , node2 int ) int {
n := len ( edges )
g := make ([][] int , n )
for i , j := range edges {
if j != - 1 {
g [ i ] = append ( g [ i ], j )
}
}
const inf int = 1 << 30
f := func ( i int ) [] int {
dist := make ([] int , n )
for j := range dist {
dist [ j ] = inf
}
dist [ i ] = 0
q := [] int { i }
for len ( q ) > 0 {
i = q [ 0 ]
q = q [ 1 :]
for _ , j := range g [ i ] {
if dist [ j ] == inf {
dist [ j ] = dist [ i ] + 1
q = append ( q , j )
}
}
}
return dist
}
d1 := f ( node1 )
d2 := f ( node2 )
ans , d := - 1 , inf
for i , a := range d1 {
b := d2 [ i ]
t := max ( a , b )
if t < d {
d = t
ans = i
}
}
return ans
}
GitHub