Query for ancestor | C # 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 ; Construct array of vector data structure for tree ; Call dfs method from root ; Method returns " yes " if u is a ancestor node of v ; Driver code
using System ; using System . Collections ; class GFG { static void dfs ( ArrayList [ ] g , int u , int parent , int [ ] timeIn , int [ ] timeOut , ref int cnt ) { timeIn [ u ] = cnt ++ ; for ( int i = 0 ; i < g [ u ] . Count ; i ++ ) { int v = ( int ) g [ u ] [ i ] ; if ( v != parent ) dfs ( g , v , u , timeIn , timeOut , ref cnt ) ; } timeOut [ u ] = cnt ++ ; } static void preProcess ( int [ , ] edges , int V , int [ ] timeIn , int [ ] timeOut ) { ArrayList [ ] g = new ArrayList [ V ] ; for ( int i = 0 ; i < V ; i ++ ) { g [ i ] = new ArrayList ( ) ; } 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 ) ; } int cnt = 0 ; dfs ( g , 0 , - 1 , timeIn , timeOut , ref cnt ) ; } static string isAncestor ( int u , int v , int [ ] timeIn , int [ ] timeOut ) { bool b = ( timeIn [ u ] <= timeIn [ v ] && timeOut [ v ] <= timeOut [ u ] ) ; return ( b ? " yes " : " no " ) ; } static void Main ( ) { int [ , ] edges = { { 0 , 1 } , { 0 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 5 } , { 4 , 6 } , { 5 , 7 } } ; int E = edges . GetLength ( 0 ) ; 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 ; Console . Write ( isAncestor ( u , v , timeIn , timeOut ) + " STRNEWLINE " ) ; u = 1 ; v = 7 ; Console . Write ( isAncestor ( u , v , timeIn , timeOut ) + " STRNEWLINE " ) ; } }