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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; adj [ v ] . push_back ( u ) ; } void DFSUtil ( int u , vector < int > adj [ ] , vector < bool > & visited , int & componentMin , int & componentMax ) { visited [ u ] = true ; componentMax = max ( componentMax , u ) ; componentMin = min ( componentMin , u ) ; for ( int i = 0 ; i < adj [ u ] . size ( ) ; i ++ ) if ( visited [ adj [ u ] [ i ] ] == false ) DFSUtil ( adj [ u ] [ i ] , adj , visited , componentMin , componentMax ) ; } bool isValid ( vector < pair < int , int > > & v ) { int MAX = -1 ; bool ans = 0 ; for ( auto i : v ) { if ( i . first <= MAX ) { ans = 1 ; } MAX = max ( MAX , i . second ) ; } return ( ans == 0 ? 1 : 0 ) ; } void DFS ( vector < int > adj [ ] , int V ) { std :: vector < pair < int , int > > v ; vector < bool > visited ( V , false ) ; for ( int u = 1 ; u <= V ; u ++ ) { if ( visited [ u ] == false ) { int componentMax = u ; int componentMin = u ; DFSUtil ( u , adj , visited , componentMin , componentMax ) ; v . push_back ( { componentMin , componentMax } ) ; } } bool check = isValid ( v ) ; if ( check ) cout << " Yes " ; else cout << " No " ; return ; } int main ( ) { int N = 4 , K = 3 ; vector < int > adj [ N + 1 ] ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 2 , 3 ) ; addEdge ( adj , 3 , 4 ) ; DFS ( adj , N ) ; return 0 ; }