Check if every vertex triplet in graph contains two vertices connected to third vertex | C # 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { class pair { public int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static void addEdge ( ArrayList adj , int u , int v ) { ( ( ArrayList ) adj [ u ] ) . Add ( v ) ; ( ( ArrayList ) adj [ v ] ) . Add ( u ) ; } static void DFSUtil ( int u , ArrayList adj , bool [ ] visited , int componentMin , int componentMax ) { visited [ u ] = true ; componentMax = Math . Max ( componentMax , u ) ; componentMin = Math . Min ( componentMin , u ) ; for ( int i = 0 ; i < ( ( ArrayList ) adj [ u ] ) . Count ; i ++ ) if ( visited [ ( int ) ( ( ArrayList ) adj [ u ] ) [ i ] ] == false ) DFSUtil ( ( int ) ( ( ArrayList ) adj [ u ] ) [ i ] , adj , visited , componentMin , componentMax ) ; } static bool isValid ( ArrayList v ) { int MAX = - 1 ; bool ans = false ; foreach ( pair i in v ) { if ( i . first <= MAX ) { ans = true ; } MAX = Math . Max ( MAX , i . second ) ; } return ( ans == false ? true : false ) ; } static void DFS ( ArrayList adj , int V ) { ArrayList v = new ArrayList ( ) ; bool [ ] visited = new bool [ 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 ) ) ; } } bool check = isValid ( v ) ; if ( check ) Console . WriteLine ( " Yes " ) ; else Console . WriteLine ( " No " ) ; return ; } public static void Main ( string [ ] args ) { int N = 4 ; ArrayList 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 ) ; } }