Make given segments non | Python3 program for the above approach ; 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
from collections import deque NEW_LINE def check ( Adj , Src , N , visited ) : NEW_LINE INDENT color = [ 0 ] * N NEW_LINE visited = [ True ] * Src NEW_LINE q = deque ( ) NEW_LINE q . append ( Src ) NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT u = q . popleft ( ) NEW_LINE Col = color [ u ] NEW_LINE for x in Adj [ u ] : NEW_LINE INDENT if ( visited [ x ] == True and color [ x ] == Col ) : NEW_LINE INDENT return False NEW_LINE DEDENT elif ( visited [ x ] == False ) : NEW_LINE INDENT visited [ x ] = True NEW_LINE q . append ( x ) NEW_LINE color [ x ] = 1 - Col NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT def addEdge ( Adj , u , v ) : NEW_LINE INDENT Adj [ u ] . append ( v ) NEW_LINE Adj [ v ] . append ( u ) NEW_LINE return Adj NEW_LINE DEDENT def isPossible ( Arr , N ) : NEW_LINE INDENT Adj = [ [ ] for i in range ( N ) ] NEW_LINE for i in range ( N - 1 ) : NEW_LINE INDENT for j in range ( i + 1 , N ) : NEW_LINE INDENT if ( Arr [ i ] [ 0 ] < Arr [ j ] [ 1 ] or Arr [ i ] [ 1 ] > Arr [ j ] [ 0 ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT if ( Arr [ i ] [ 2 ] == Arr [ j ] [ 2 ] ) : NEW_LINE INDENT Adj = addEdge ( Adj , i , j ) NEW_LINE DEDENT DEDENT DEDENT DEDENT visited = [ False ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( visited [ i ] == False and len ( Adj [ i ] ) > 0 ) : NEW_LINE INDENT if ( check ( Adj , i , N , visited ) == False ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT print ( " Yes " ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 5 , 7 , 2 ] , [ 4 , 6 , 1 ] , [ 1 , 5 , 2 ] , [ 6 , 5 , 1 ] ] NEW_LINE N = len ( arr ) NEW_LINE isPossible ( arr , N ) NEW_LINE DEDENT