Query for ancestor | Python 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
cnt = 0 NEW_LINE def dfs ( g : list , u : int , parent : int , timeIn : list , timeOut : list ) : NEW_LINE INDENT global cnt NEW_LINE timeIn [ u ] = cnt NEW_LINE cnt += 1 NEW_LINE for i in range ( len ( g [ u ] ) ) : NEW_LINE INDENT v = g [ u ] [ i ] NEW_LINE if v != parent : NEW_LINE INDENT dfs ( g , v , u , timeIn , timeOut ) NEW_LINE DEDENT DEDENT timeOut [ u ] = cnt NEW_LINE cnt += 1 NEW_LINE DEDENT def preProcess ( edges : list , V : int , timeIn : list , timeOut : list ) : NEW_LINE INDENT global cnt NEW_LINE g = [ [ ] for i in range ( V ) ] NEW_LINE for i in range ( V - 1 ) : NEW_LINE INDENT u = edges [ i ] [ 0 ] NEW_LINE v = edges [ i ] [ 1 ] NEW_LINE g [ u ] . append ( v ) NEW_LINE g [ v ] . append ( u ) NEW_LINE DEDENT cnt = 0 NEW_LINE dfs ( g , 0 , - 1 , timeIn , timeOut ) NEW_LINE DEDENT def isAncestor ( u : int , v : int , timeIn : list , timeOut : list ) -> str : NEW_LINE INDENT b = timeIn [ u ] <= timeIn [ u ] and timeOut [ v ] <= timeOut [ u ] NEW_LINE return " yes " if b else " no " NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT edges = [ ( 0 , 1 ) , ( 0 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 5 ) , ( 4 , 6 ) , ( 5 , 7 ) ] NEW_LINE E = len ( edges ) NEW_LINE V = E + 1 NEW_LINE timeIn = [ 0 ] * V NEW_LINE timeOut = [ 0 ] * V NEW_LINE preProcess ( edges , V , timeIn , timeOut ) NEW_LINE u = 1 NEW_LINE v = 6 NEW_LINE print ( isAncestor ( u , v , timeIn , timeOut ) ) NEW_LINE u = 1 NEW_LINE v = 7 NEW_LINE print ( isAncestor ( u , v , timeIn , timeOut ) ) NEW_LINE DEDENT