Find the winner of the match | Multiple Queries | C ++ program to find winner of the match ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void add ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; } vector < int > topo ( vector < int > adj [ ] , int n ) { vector < int > indeg ( n , 0 ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( auto x : adj [ i ] ) indeg [ x ] ++ ; } vector < int > answer ; vector < bool > visited ( n , false ) ; queue < int > q ; for ( int i = 0 ; i < n ; i ++ ) { if ( indeg [ i ] == 0 ) { q . push ( i ) ; visited [ i ] = true ; } } while ( ! q . empty ( ) ) { int u = q . front ( ) ; answer . push_back ( u ) ; q . pop ( ) ; for ( auto x : adj [ u ] ) { indeg [ x ] -- ; if ( indeg [ x ] == 0 && ! visited [ x ] ) { q . push ( x ) ; visited [ x ] = true ; } } } return answer ; } int who_wins ( vector < int > topotable , int u , int v ) { for ( auto x : topotable ) { if ( x == u ) return u ; if ( x == v ) return v ; } } int main ( ) { vector < int > adj [ 10 ] ; int n = 7 ; add ( adj , 0 , 1 ) ; add ( adj , 0 , 2 ) ; add ( adj , 0 , 3 ) ; add ( adj , 1 , 5 ) ; add ( adj , 2 , 5 ) ; add ( adj , 3 , 4 ) ; add ( adj , 4 , 5 ) ; add ( adj , 6 , 0 ) ; vector < int > topotable = topo ( adj , n ) ; cout << who_wins ( topotable , 3 , 5 ) << endl ; cout << who_wins ( topotable , 1 , 2 ) << endl ; return 0 ; }