Find the winner of the match | Multiple Queries | Function to add edge between two nodes ; Function returns topological order of given graph ; Indeg vector will store indegrees of all vertices ; Answer vector will have our final topological order ; Visited will be true if that vertex has been visited ; q will store the vertices that have indegree equal to zero ; Iterate till queue is not empty ; Push the front of queue to answer ; For all neighbours of u , decrement their indegree value ; If indegree of any vertex becomes zero and it is not marked then push it to queue ; Mark this vertex as visited ; Return the resultant topological order ; Function to return the winner between u and v ; Player who comes first wins ; Driver code ; Total number of players ; Build the graph add ( adj , x , y ) means x wins over y ; Resultant topological order in topotable ; Queries
def add ( adj , u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE DEDENT def topo ( adj , n ) : NEW_LINE INDENT indeg = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for x in adj [ i ] : NEW_LINE INDENT indeg [ x ] += 1 NEW_LINE DEDENT DEDENT answer = [ ] NEW_LINE visited = [ False for i in range ( n ) ] NEW_LINE q = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( indeg [ i ] == 0 ) : NEW_LINE INDENT q . append ( i ) NEW_LINE visited [ i ] = True NEW_LINE DEDENT DEDENT while ( len ( q ) != 0 ) : NEW_LINE INDENT u = q [ 0 ] NEW_LINE answer . append ( u ) NEW_LINE q . remove ( q [ 0 ] ) NEW_LINE for x in adj [ u ] : NEW_LINE INDENT indeg [ x ] -= 1 NEW_LINE if ( indeg [ x ] == 0 and visited [ x ] == False ) : NEW_LINE INDENT q . append ( x ) NEW_LINE visited [ x ] = True NEW_LINE DEDENT DEDENT DEDENT return answer NEW_LINE DEDENT def who_wins ( topotable , u , v ) : NEW_LINE INDENT for x in topotable : NEW_LINE INDENT if ( x == u ) : NEW_LINE INDENT return u NEW_LINE DEDENT if ( x == v ) : NEW_LINE INDENT return v NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT adj = [ [ ] for i in range ( 10 ) ] NEW_LINE n = 7 NEW_LINE add ( adj , 0 , 1 ) NEW_LINE add ( adj , 0 , 2 ) NEW_LINE add ( adj , 0 , 3 ) NEW_LINE add ( adj , 1 , 5 ) NEW_LINE add ( adj , 2 , 5 ) NEW_LINE add ( adj , 3 , 4 ) NEW_LINE add ( adj , 4 , 5 ) NEW_LINE add ( adj , 6 , 0 ) NEW_LINE topotable = topo ( adj , n ) NEW_LINE print ( who_wins ( topotable , 3 , 5 ) ) NEW_LINE print ( who_wins ( topotable , 1 , 2 ) ) NEW_LINE DEDENT