Make given segments non | 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 ; Initialize ; 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
class Node { constructor ( L , R , V ) { this . L = L ; this . R = R ; this . V = V ; } } function check ( Adj , Src , N , visited ) { let color = new Array ( N ) ; visited [ Src ] = true ; let q = [ ] ; q . push ( Src ) ; while ( q . length != 0 ) { let u = q . shift ( ) ; let Col = color [ u ] ; for ( let x = 0 ; x < Adj [ u ] . length ; x ++ ) { if ( visited [ Adj [ u ] [ x ] ] == true && color [ Adj [ u ] [ x ] ] == Col ) { return false ; } else if ( visited [ Adj [ u ] [ x ] ] == false ) { visited [ Adj [ u ] [ x ] ] = true ; q . push ( Adj [ u ] [ x ] ) ; color [ Adj [ u ] [ x ] ] = 1 - Col ; } } } return true ; } function addEdge ( Adj , u , v ) { Adj [ u ] . push ( v ) ; Adj [ v ] . push ( u ) ; } function isPossible ( Arr , N ) { let Adj = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) Adj [ i ] = [ ] ; for ( let i = 0 ; i < N - 1 ; i ++ ) { for ( let 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 ) ; } } } } let visited = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) visited [ i ] = false ; for ( let i = 0 ; i < N ; i ++ ) { if ( visited [ i ] == false && Adj [ i ] . length > 0 ) { if ( check ( Adj , i , N , visited ) == false ) { document . write ( " " ) ; return ; } } } document . write ( " " ) ; } let arr = [ new Node ( 5 , 7 , 2 ) , new Node ( 4 , 6 , 1 ) , new Node ( 1 , 5 , 2 ) , new Node ( 6 , 5 , 1 ) ] ; let N = arr . length ; isPossible ( arr , N ) ;