text: Make given segments non | C ++ program for the above approach ; Stores the details of the Segment ; Function to check whether the graph is bipartite or not ; Mark source node as visited ; Push the source vertex in queue ; Get the front of the queue ; Assign the color to the popped node ; Traverse the adjacency list of the node u ; If any node is visited & a different colors has been assigned , then return false ; Set visited [ x ] ; Push the node x into the queue ; Update color of node ; If the graph is bipartite ; Function to add an edge between the nodes u and v ; Function to check if the assignment of direction can be possible to all the segments , such that they do not intersect after a long period of time ; Stores the adjacency list of the created graph ; Generate all possible pairs ; If segments do not overlap ; Otherwise , the segments overlap ; If both segments have same speed , then add an edge ; Keep the track of visited nodes ; Iterate for all possible nodes ; Check whether graph is bipartite or not ; If the graph is bipartite ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int L , R , V ; } ; bool check ( vector < int > Adj [ ] , int Src , int N , bool visited [ ] ) { int color [ N ] = { 0 } ; visited [ Src ] = true ; queue < int > q ; q . push ( Src ) ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; int Col = color [ u ] ; for ( int x : Adj [ u ] ) { if ( visited [ x ] == true && color [ x ] == Col ) { return false ; } else if ( visited [ x ] == false ) { visited [ x ] = true ; q . push ( x ) ; color [ x ] = 1 - Col ; } } } return true ; } void addEdge ( vector < int > Adj [ ] , int u , int v ) { Adj [ u ] . push_back ( v ) ; Adj [ v ] . push_back ( u ) ; } void isPossible ( struct Node Arr [ ] , int N ) { vector < int > Adj [ N ] ; for ( int i = 0 ; i < N - 1 ; i ++ ) { for ( int j = i + 1 ; j < N ; j ++ ) { if ( Arr [ i ] . R < Arr [ j ] . L Arr [ i ] . L > Arr [ j ] . R ) { continue ; } else { if ( Arr [ i ] . V == Arr [ j ] . V ) { addEdge ( Adj , i , j ) ; } } } } bool visited [ N ] = { false } ; for ( int i = 0 ; i < N ; i ++ ) { if ( visited [ i ] == false && Adj [ i ] . size ( ) > 0 ) { if ( check ( Adj , i , N , visited ) == false ) { cout << " No " ; return ; } } } cout << " Yes " ; } int main ( ) { struct Node arr [ ] = { { 5 , 7 , 2 } , { 4 , 6 , 1 } , { 1 , 5 , 2 } , { 6 , 5 , 1 } } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; isPossible ( arr , N ) ; return 0 ; }