Check if every vertex triplet in graph contains two vertices connected to third vertex | Function to add edge into the graph ; Finding the maximum and minimum values in each component ; Function for checking whether the given graph is valid or not ; Checking for intersecting intervals ; If intersection is found ; Graph is not valid ; Function for the DFS Traversal ; Traversing for every vertex ; Storing maximum and minimum values of each component ; Driver code
def addEdge ( adj , u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE return adj NEW_LINE DEDENT def DFSUtil ( u , adj , visited , componentMin , componentMax ) : NEW_LINE INDENT visited [ u ] = True NEW_LINE componentMax = max ( componentMax , u ) NEW_LINE componentMin = min ( componentMin , u ) NEW_LINE for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( visited [ adj [ u ] [ i ] ] == False ) : NEW_LINE INDENT visited , componentMax , componentMin = DFSUtil ( adj [ u ] [ i ] , adj , visited , componentMin , componentMax ) NEW_LINE DEDENT DEDENT return visited , componentMax , componentMin NEW_LINE DEDENT def isValid ( v ) : NEW_LINE INDENT MAX = - 1 NEW_LINE ans = False NEW_LINE for i in v : NEW_LINE INDENT if len ( i ) != 2 : NEW_LINE INDENT continue NEW_LINE DEDENT if ( i [ 0 ] <= MAX ) : NEW_LINE INDENT ans = True NEW_LINE DEDENT MAX = max ( MAX , i [ 1 ] ) NEW_LINE DEDENT return ( True if ans == False else False ) NEW_LINE DEDENT def DFS ( adj , V ) : NEW_LINE INDENT v = [ [ ] ] NEW_LINE visited = [ False for i in range ( V + 1 ) ] NEW_LINE for u in range ( 1 , V + 1 ) : NEW_LINE INDENT if ( visited [ u ] == False ) : NEW_LINE INDENT componentMax = u NEW_LINE componentMin = u NEW_LINE visited , componentMax , componentMin = DFSUtil ( u , adj , visited , componentMin , componentMax ) NEW_LINE v . append ( [ componentMin , componentMax ] ) NEW_LINE DEDENT DEDENT check = isValid ( v ) NEW_LINE if ( check ) : NEW_LINE INDENT print ( ' Yes ' ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ' No ' ) NEW_LINE DEDENT return NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 NEW_LINE K = 3 NEW_LINE adj = [ [ ] for i in range ( N + 1 ) ] NEW_LINE adj = addEdge ( adj , 1 , 2 ) NEW_LINE adj = addEdge ( adj , 2 , 3 ) NEW_LINE adj = addEdge ( adj , 3 , 4 ) NEW_LINE DFS ( adj , N ) NEW_LINE DEDENT