Dada una array de pares arr de tamaño N que representa una situación de juego en la que el primer jugador gana contra el segundo jugador. Dadas múltiples consultas, cada consulta contiene dos números, la tarea es determinar cuál de ellos ganará si compiten entre sí.
NOTA:
- Si A gana sobre B y B gana sobre C , entonces A siempre ganará sobre C.
- Si A gana sobre B y A gana sobre C , si hay un partido contra B y C y si no podemos determinar el ganador, entonces gana el jugador con el número más pequeño.
Ejemplos:
Entrada: arr[] = {{0, 1}, {0, 2}, {0, 3}, {1, 5}, {2, 5}, {3, 4}, {4, 5}, { 6, 0}}
consulta[] = {{3, 5}, {1, 2}}
Salida: 3
1
Explicación: 3 gana sobre 4 y 4 gana sobre 5. Entonces, 3 es el ganador en el primer partido.
No podemos determinar el ganador entre 1 y 2. Entonces, el jugador con un número menor es el ganador, es decir, 1
Entrada: arr[] = {{0, 1}, {0, 2}, {0, 3} , {1, 5}, {2, 5}, {3, 4}, {4, 5}, {6, 0}}
consulta[] = {{0, 5}, {0, 6}}
Salida: 0
6
Requisitos previos: enfoque de clasificación topológica : supongamos que todas las entradas son válidas. Ahora construye un gráfico. Si el jugador X gana al jugador Y, agregamos una ventaja del jugador X al jugador Y. Después de construir el gráfico, realice la clasificación topológica. Para cada consulta de la forma (x, y) verificamos qué número x o y viene antes en el ordenamiento topológico e imprimimos la respuesta. A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find winner of the match
#include <bits/stdc++.h>
using namespace std;
// Function to add edge between two nodes
void add(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
}
// Function returns topological order of given graph
vector<int> topo(vector<int> adj[], int n)
{
// Indeg vector will store
// indegrees of all vertices
vector<int> indeg(n, 0);
for (int i = 0; i < n; i++) {
for (auto x : adj[i])
indeg[x]++;
}
// Answer vector will have our
// final topological order
vector<int> answer;
// Visited will be true if that
// vertex has been visited
vector<bool> visited(n, false);
// q will store the vertices
// that have indegree equal to zero
queue<int> q;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) {
q.push(i);
visited[i] = true;
}
}
// Iterate till queue is not empty
while (!q.empty()) {
int u = q.front();
// Push the front of queue to answer
answer.push_back(u);
q.pop();
// For all neighbours of u, decrement
// their indegree value
for (auto x : adj[u]) {
indeg[x]--;
// If indegree of any vertex becomes zero and
// it is not marked then push it to queue
if (indeg[x] == 0 && !visited[x]) {
q.push(x);
// Mark this vertex as visited
visited[x] = true;
}
}
}
// Return the resultant topological order
return answer;
}
// Function to return the winner between u and v
int who_wins(vector<int> topotable, int u, int v)
{
// Player who comes first wins
for (auto x : topotable) {
if (x == u)
return u;
if (x == v)
return v;
}
}
// Driver code
int main()
{
vector<int> adj[10];
// Total number of players
int n = 7;
// Build the graph
// add(adj, x, y) means x wins over y
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);
// Resultant topological order in topotable
vector<int> topotable = topo(adj, n);
// Queries
cout << who_wins(topotable, 3, 5) << endl;
cout << who_wins(topotable, 1, 2) << endl;
return 0;
}
Python3
# Python3 program to find winner of the match # Function to add edge between two nodes def add(adj, u, v): adj[u].append(v) # Function returns topological order of given graph def topo(adj, n): # Indeg vector will store # indegrees of all vertices indeg = [0 for i in range(n)] for i in range(n): for x in adj[i]: indeg[x] += 1 # Answer vector will have our # final topological order answer = [] # Visited will be true if that # vertex has been visited visited = [False for i in range(n)] # q will store the vertices # that have indegree equal to zero q = [] for i in range(n): if (indeg[i] == 0): q.append(i) visited[i] = True # Iterate till queue is not empty while (len(q) != 0): u = q[0] # Push the front of queue to answer answer.append(u) q.remove(q[0]) # For all neighbours of u, decrement # their indegree value for x in adj[u]: indeg[x] -= 1 # If indegree of any vertex becomes zero and # it is not marked then push it to queue if (indeg[x] == 0 and visited[x] == False): q.append(x) # Mark this vertex as visited visited[x] = True # Return the resultant topological order return answer # Function to return the winner between u and v def who_wins(topotable, u, v): # Player who comes first wins for x in topotable: if (x == u): return u if (x == v): return v # Driver code if __name__ == '__main__': adj = [[] for i in range(10)] # Total number of players n = 7 # Build the graph # add(adj, x, y) means x wins over y 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) # Resultant topological order in topotable topotable = topo(adj, n) # Queries print(who_wins(topotable, 3, 5)) print(who_wins(topotable, 1, 2)) # This code is contributed by Surendra_Gangwar
Javascript
<script>
brbr// JavaScript program to find winner of the match
// Function to add edge between two nodes
function add(adj, u, v){
adj[u].push(v)
}
// Function returns topological order of given graph
function topo(adj, n){
// Indeg vector will store
// indegrees of all vertices
let indeg = new Array(n).fill(0)
for(let i=0;i<n;i++){
for(let x of adj[i]){
indeg[x] += 1
}
}
// Answer vector will have our
// final topological order
let answer = []
// Visited will be true if that
// vertex has been visited
let visited = new Array(n).fill(false)
// q will store the vertices
// that have indegree equal to zero
let q = []
for(let i=0;i<n;i++){
if (indeg[i] == 0){
q.push(i)
visited[i] = true
}
}
// Iterate till queue is not empty
while (q.length != 0){
let u = q.shift()
// Push the front of queue to answer
answer.push(u)
// For all neighbours of u, decrement
// their indegree value
for(let x of adj[u]){
indeg[x] -= 1
// If indegree of any vertex becomes zero and
// it is not marked then push it to queue
if (indeg[x] == 0 && visited[x] == false){
q.push(x)
// Mark this vertex as visited
visited[x] = true
}
}
}
// Return the resultant topological order
return answer
}
// Function to return the winner between u and v
function who_wins(topotable, u, v){
// Player who comes first wins
for(let x of topotable){
if (x == u)
return u
if (x == v)
return v
}
}
// Driver code
let adj = new Array(10).fill(0).map(()=>new Array())
// Total number of players
let n = 7
// Build the graph
// add(adj, x, y) means x wins over y
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)
// Resultant topological order in topotable
let topotable = topo(adj, n)
// Queries
document.write(who_wins(topotable, 3, 5),"</br>")
document.write(who_wins(topotable, 1, 2),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción:
3 1