Query for ancestor | Java program to query whether two node has ancestor - descendant relationship or not ; Utility dfs method to assign in and out time to each node ; Assign In - time to node u ; Call dfs over all neighbors except parent ; Assign Out - time to node u ; Method to preprocess all nodes for assigning time ; Conarray of vector data structure for tree ; Call dfs method from root ; Method returns " yes " if u is a ancestor node of v ; Driver code
import java . util . Vector ; class GFG { static int cnt ; static void dfs ( Vector < Integer > [ ] g , int u , int parent , int [ ] timeIn , int [ ] timeOut ) { timeIn [ u ] = cnt ++ ; for ( int i = 0 ; i < g [ u ] . size ( ) ; i ++ ) { int v = g [ u ] . get ( i ) ; if ( v != parent ) dfs ( g , v , u , timeIn , timeOut ) ; } timeOut [ u ] = cnt ++ ; } static void preProcess ( int [ ] [ ] edges , int V , int [ ] timeIn , int [ ] timeOut ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] g = new Vector [ V ] ; for ( int i = 0 ; i < g . length ; i ++ ) g [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < V - 1 ; i ++ ) { int u = edges [ i ] [ 0 ] ; int v = edges [ i ] [ 1 ] ; g [ u ] . add ( v ) ; g [ v ] . add ( u ) ; } cnt = 0 ; dfs ( g , 0 , - 1 , timeIn , timeOut ) ; } static String isAncestor ( int u , int v , int [ ] timeIn , int [ ] timeOut ) { boolean b = ( timeIn [ u ] <= timeIn [ v ] && timeOut [ v ] <= timeOut [ u ] ) ; return ( b ? " yes " : " no " ) ; } public static void main ( String [ ] args ) { int edges [ ] [ ] = { { 0 , 1 } , { 0 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 5 } , { 4 , 6 } , { 5 , 7 } } ; int E = edges . length ; int V = E + 1 ; int [ ] timeIn = new int [ V ] ; int [ ] timeOut = new int [ V ] ; preProcess ( edges , V , timeIn , timeOut ) ; int u = 1 ; int v = 6 ; System . out . println ( isAncestor ( u , v , timeIn , timeOut ) ) ; u = 1 ; v = 7 ; System . out . println ( isAncestor ( u , v , timeIn , timeOut ) ) ; } }