Check if every vertex triplet in graph contains two vertices connected to third vertex | JavaScript program of the above approach ; 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
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function addEdge ( adj , u , v ) { ( adj [ u ] ) . push ( v ) ; ( adj [ v ] ) . push ( u ) ; } function DFSUtil ( u , adj , visited , componentMin , componentMax ) { visited [ u ] = true ; componentMax = Math . max ( componentMax , u ) ; componentMin = Math . min ( componentMin , u ) ; for ( var i = 0 ; i < ( adj [ u ] ) . length ; i ++ ) if ( visited [ ( adj [ u ] ) [ i ] ] == false ) DFSUtil ( ( adj [ u ] ) [ i ] , adj , visited , componentMin , componentMax ) ; } function isValid ( v ) { var MAX = - 1 ; var ans = false ; for ( var i of v ) { if ( i . first <= MAX ) { ans = true ; } MAX = Math . max ( MAX , i . second ) ; } return ( ans == false ? true : false ) ; } function DFS ( adj , V ) { var v = [ ] ; var visited = Array ( V + 1 ) . fill ( false ) ; for ( var u = 1 ; u <= V ; u ++ ) { if ( visited [ u ] == false ) { var componentMax = u ; var componentMin = u ; DFSUtil ( u , adj , visited , componentMin , componentMax ) ; v . push ( new pair ( componentMin , componentMax ) ) ; } } var check = isValid ( v ) ; if ( check ) document . write ( " " ) ; else document . write ( " " ) ; return ; } var N = 4 ; var adj = [ ] ; for ( var i = 0 ; i <= N + 1 ; i ++ ) adj . push ( new Array ( ) ) ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 2 , 3 ) ; addEdge ( adj , 3 , 4 ) ; DFS ( adj , N ) ;