Check if every vertex triplet in graph contains two vertices connected to third vertex | Java 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
import java . util . * ; import java . lang . * ; class GFG { static class pair { int first , second ; pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void addEdge ( ArrayList < ArrayList < Integer > > adj , int u , int v ) { adj . get ( u ) . add ( v ) ; adj . get ( v ) . add ( u ) ; } static void DFSUtil ( int u , ArrayList < ArrayList < Integer > > adj , boolean [ ] visited , int componentMin , int componentMax ) { visited [ u ] = true ; componentMax = Math . max ( componentMax , u ) ; componentMin = Math . min ( componentMin , u ) ; for ( int i = 0 ; i < adj . get ( u ) . size ( ) ; i ++ ) if ( visited [ adj . get ( u ) . get ( i ) ] == false ) DFSUtil ( adj . get ( u ) . get ( i ) , adj , visited , componentMin , componentMax ) ; } static boolean isValid ( ArrayList < pair > v ) { int MAX = - 1 ; boolean ans = false ; for ( pair i : v ) { if ( i . first <= MAX ) { ans = true ; } MAX = Math . max ( MAX , i . second ) ; } return ( ans == false ? true : false ) ; } static void DFS ( ArrayList < ArrayList < Integer > > adj , int V ) { ArrayList < pair > v = new ArrayList < > ( ) ; boolean [ ] visited = new boolean [ V + 1 ] ; for ( int u = 1 ; u <= V ; u ++ ) { if ( visited [ u ] == false ) { int componentMax = u ; int componentMin = u ; DFSUtil ( u , adj , visited , componentMin , componentMax ) ; v . add ( new pair ( componentMin , componentMax ) ) ; } } boolean check = isValid ( v ) ; if ( check ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; return ; } public static void main ( String [ ] args ) { int N = 4 , K = 3 ; ArrayList < ArrayList < Integer > > adj = new ArrayList < > ( ) ; for ( int i = 0 ; i <= N + 1 ; i ++ ) adj . add ( new ArrayList < > ( ) ) ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 2 , 3 ) ; addEdge ( adj , 3 , 4 ) ; DFS ( adj , N ) ; } }