text: Make given segments non | Java 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 ; 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
code: import java . io . * ; import java . lang . * ; import java . util . * ; class GFG { static class Node { int L , R , V ; Node ( int L , int R , int V ) { this . L = L ; this . R = R ; this . V = V ; } } static boolean check ( ArrayList < Integer > Adj [ ] , int Src , int N , boolean visited [ ] ) { int color [ ] = new int [ N ] ; visited [ Src ] = true ; ArrayDeque < Integer > q = new ArrayDeque < > ( ) ; q . addLast ( Src ) ; while ( ! q . isEmpty ( ) ) { int u = q . removeFirst ( ) ; 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 . addLast ( x ) ; color [ x ] = 1 - Col ; } } } return true ; } static void addEdge ( ArrayList < Integer > Adj [ ] , int u , int v ) { Adj [ u ] . add ( v ) ; Adj [ v ] . add ( u ) ; } static void isPossible ( Node Arr [ ] , int N ) { @ SuppressWarnings ( " unchecked " ) ArrayList < Integer > [ ] Adj = ( ArrayList < Integer > [ ] ) new ArrayList [ N ] ; for ( int i = 0 ; i < N ; i ++ ) Adj [ i ] = new ArrayList < > ( ) ; 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 ) ; } } } } boolean visited [ ] = new boolean [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { if ( visited [ i ] == false && Adj [ i ] . size ( ) > 0 ) { if ( check ( Adj , i , N , visited ) == false ) { System . out . println ( " No " ) ; return ; } } } System . out . println ( " Yes " ) ; } public static void main ( String [ ] args ) { Node arr [ ] = { new Node ( 5 , 7 , 2 ) , new Node ( 4 , 6 , 1 ) , new Node ( 1 , 5 , 2 ) , new Node ( 6 , 5 , 1 ) } ; int N = arr . length ; isPossible ( arr , N ) ; } }