Dado un árbol con N Nodes. Dos jugadores A y B comienzan desde el Node 1 y el Node N respectivamente. A puede visitar todos los Nodes adyacentes a los Nodes ya visitados por A pero no puede visitar ningún Node que ya haya sido visitado por B y de manera similar para B también.
Gana el jugador que visita más ciudades. Encuentra el jugador que gana si ambos juegan de manera óptima.
Ejemplos:
Input:
Output: A wins
Enfoque: la solución óptima es que tanto el jugador comience a visitar los Nodes que se encuentran en la ruta que conecta el Node 1 y el Node N. Esto se debe a que un jugador no puede visitar los Nodes que ya visitó otro jugador, por lo que cada jugador intentará limitar la cantidad de Nodes que puede visitar otro jugador. Entonces será fácil contar la cantidad de Nodes que puede visitar cada jugador y descubrir el ganador.
El DFS se usará para encontrar la ruta entre dos Nodes y marcarlos uno por uno como 1 o 2, 1 para A y 2 para B y luego marcar todos los Nodes adyacentes no visitados con el valor respectivo y luego calcular el conteo de Nodes de A y B.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Vector to store Tree
vector<vector<int> > graph;
// To check if there
// is path or not
int found = 0, n;
// Path and temporary vector
vector<int> path, temp;
// Count of A and B
int c_A = 0, c_B = 0;
// Function to find the path connecting 1 to n
void find(int i, int prev)
{
// Push the ith node
temp.push_back(i);
// If we reached our destination
if (i == n) {
path = (temp);
return;
}
for (int j = 0; j < graph[i].size(); j++)
if (graph[i][j] != prev) {
// Dfs for its children
find(graph[i][j], i);
}
// Remove the node
temp.pop_back();
}
// Function to mark all the adjacent
// unvisited nodes
void mark(int i, int visited[], int c)
{
if (!visited[i]) {
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
}
visited[i] = c;
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
// Dfs for all its unvisited adjacent nodes
for (int j = 0; j < graph[i].size(); j++)
if (!visited[graph[i][j]])
mark(graph[i][j], visited, c);
}
// Function to find the winner among the players
void findWinner()
{
// Finds the path
find(1, -1);
int visited[n + 1] = { 0 };
for (int i = 0; i < path.size(); i++) {
// Mark nodes visited by
// A as 1 and B as 2
if (i < ceil(path.size() / 2.0))
visited[path[i]] = 1, c_A++;
else
visited[path[i]] = 2, c_B++;
}
// Mark all the adjacent unvisited nodes
for (int i = 0; i < path.size(); i++)
mark(path[i],
visited,
visited[path[i]]);
if (c_A > c_B)
cout << "A wins";
else if (c_A < c_B)
cout << "B wins";
else
cout << "Draw";
}
// Driver code
int main()
{
n = 7;
graph.clear();
graph.resize(n + 1);
// Graph
graph[6].push_back(4);
graph[4].push_back(6);
graph[6].push_back(5);
graph[5].push_back(6);
graph[5].push_back(7);
graph[7].push_back(5);
graph[5].push_back(2);
graph[2].push_back(5);
graph[3].push_back(4);
graph[4].push_back(3);
graph[1].push_back(4);
graph[4].push_back(1);
findWinner();
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
// Vector to store Tree
static Vector<Integer> []graph;
// To check if there
// is path or not
static int found = 0, n;
// Path and temporary vector
static Vector<Integer> path =
new Vector<>();
static Vector<Integer> temp =
new Vector<>();
// Count of A and B
static int c_A = 0, c_B = 0;
// Function to find the path
// connecting 1 to n
static void find(int i,
int prev)
{
// Push the ith node
temp.add(i);
// If we reached our
// destination
if (i == n)
{
path = (temp);
return;
}
for (int j = 0;
j < graph[i].size(); j++)
if (graph[i].get(j) != prev)
{
// Dfs for its children
find(graph[i].get(j), i);
}
// Remove the node
temp.remove(temp.size() - 1);
}
// Function to mark all the
// adjacent unvisited nodes
static void mark(int i,
int visited[],
int c)
{
if (visited[i] > 0)
{
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
}
visited[i] = c;
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
// Dfs for all its unvisited
// adjacent nodes
for (int j = 0;
j < graph[i].size(); j++)
if (visited[graph[i].get(j)] > 0)
mark(graph[i].get(j),
visited, c);
}
// Function to find the winner
// among the players
static void findWinner()
{
// Finds the path
find(1, -1);
int visited[] = new int[n + 1];
for (int i = 0;
i < path.size(); i++)
{
// Mark nodes visited by
// A as 1 and B as 2
if (i < Math.ceil(path.size() / 2.0))
{
visited[path.get(i)] = 1;
c_A++;
}
else
{
visited[path.get(i)] = 2;
c_B++;
}
}
// Mark all the adjacent
// unvisited nodes
for (int i = 0;
i < path.size(); i++)
mark(path.get(i),
visited,
visited[path.get(i)]);
if (c_A > c_B)
System.out.print("A wins");
else if (c_A < c_B)
System.out.print("B wins");
else
System.out.print("Draw");
}
// Driver code
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
n = 7;
graph = new Vector[n + 1];
for (int i = 0;
i < graph.length; i++)
graph[i] = new Vector<Integer>();
// Graph
graph[6].add(4);
graph[4].add(6);
graph[6].add(5);
graph[5].add(6);
graph[5].add(7);
graph[7].add(5);
graph[5].add(2);
graph[2].add(5);
graph[3].add(4);
graph[4].add(3);
graph[1].add(4);
graph[4].add(1);
findWinner();
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation of the above approach
from math import ceil, floor
# Vector to store Tree
graph = [[] for i in range(1000)]
# To check if there
# is path or not
found = 0
n = 0
# Path and temporary vector
path = []
temp = []
# Count of A and B
c_A = 0
c_B = 0
# Function to find the path connecting 1 to n
def find(i, prev):
global c_A, c_B, path
# Push the ith node
temp.append(i)
# If we reached our destination
if (i == n):
path = temp
return
for j in graph[i]:
if j != prev:
# Dfs for its children
find(j, i)
# Remove the node
del temp[-1]
# Function to mark all the adjacent
# unvisited nodes
def mark(i, visited, c):
global c_B, c_A
if visited[i] == 0:
# Increase the count
if (c == 1):
c_A += 1
else:
c_B += 1
visited[i] = c
# Increase the count
if (c == 1):
c_A += 1
else:
c_B += 1
# Dfs for all its unvisited adjacent nodes
for j in graph[i]:
if (visited[j] == 0):
mark(j, visited, c)
# Function to find the winner among the players
def findWinner():
global c_B, c_A, path
# Finds the path
find(1, -1)
visited = [0 for i in range(n + 1)]
for i in range(len(path)):
# Mark nodes visited by
# A as 1 and B as 2
if (i < ceil(len(path) / 2.0)):
visited[path[i]] = 1
c_A += 1
else:
visited[path[i]] = 2
c_B += 1
# Mark all the adjacent unvisited nodes
for i in path:
mark(i, visited, visited[i])
if (c_A > c_B):
print("A wins")
elif (c_A < c_B):
print("B wins")
else:
print("Draw")
# Driver code
n = 7
# Graph
graph[6].append(4)
graph[4].append(6)
graph[6].append(5)
graph[5].append(6)
graph[5].append(7)
graph[7].append(5)
graph[5].append(2)
graph[2].append(5)
graph[3].append(4)
graph[4].append(3)
graph[1].append(4)
graph[4].append(1)
findWinner()
# This code is contributed by Mohit Kumar
C#
// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// List to store Tree
static List<int> []graph;
// To check if there
// is path or not
static int found = 0, n;
// Path and temporary vector
static List<int> path =
new List<int>();
static List<int> temp =
new List<int>();
// Count of A and B
static int c_A = 0, c_B = 0;
// Function to find the path
// connecting 1 to n
static void find(int i,
int prev)
{
// Push the ith node
temp.Add(i);
// If we reached our
// destination
if (i == n)
{
path = (temp);
return;
}
for (int j = 0;
j < graph[i].Count; j++)
if (graph[i][j] != prev)
{
// Dfs for its children
find(graph[i][j], i);
}
// Remove the node
temp.Remove(temp.Count - 1);
}
// Function to mark all the
// adjacent unvisited nodes
static void mark(int i,
int []visited,
int c)
{
if (visited[i] > 0)
{
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
}
visited[i] = c;
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
// Dfs for all its unvisited
// adjacent nodes
for (int j = 0;
j < graph[i].Count; j++)
if (visited[graph[i][j]] > 0)
mark(graph[i][j],
visited, c);
}
// Function to find the winner
// among the players
static void findWinner()
{
// Finds the path
find(1, -1);
int []visited = new int[n + 1];
for (int i = 0;
i < path.Count; i++)
{
// Mark nodes visited by
// A as 1 and B as 2
if (i < Math.Ceiling(path.Count / 2.0))
{
visited[path[i]] = 1;
c_A++;
}
else
{
visited[path[i]] = 2;
c_B++;
}
}
// Mark all the adjacent
// unvisited nodes
for (int i = 0;
i < path.Count; i++)
mark(path[i],
visited,
visited[path[i]]);
if (c_A > c_B)
Console.Write("A wins");
else if (c_A < c_B)
Console.Write("B wins");
else
Console.Write("Draw");
}
// Driver code
public static void Main(String[] args)
{
n = 7;
graph = new List<int>[n + 1];
for (int i = 0;
i < graph.Length; i++)
graph[i] = new List<int>();
// Graph
graph[6].Add(4);
graph[4].Add(6);
graph[6].Add(5);
graph[5].Add(6);
graph[5].Add(7);
graph[7].Add(5);
graph[5].Add(2);
graph[2].Add(5);
graph[3].Add(4);
graph[4].Add(3);
graph[1].Add(4);
graph[4].Add(1);
findWinner();
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the
// above approach
// Vector to store Tree
let graph;
// To check if there
// is path or not
let found = 0, n;
// Path and temporary vector
let path = [];
let temp = [];
// Count of A and B
let c_A = 0, c_B = 0;
// Function to find the path
// connecting 1 to n
function find(i, prev)
{
// Push the ith node
temp.push(i);
// If we reached our
// destination
if (i == n)
{
path = (temp);
return;
}
for(let j = 0;
j < graph[i].length; j++)
{
if (graph[i][j] != prev)
{
// Dfs for its children
find(graph[i][j], i);
}
}
// Remove the node
temp.pop();
}
// Function to mark all the
// adjacent unvisited nodes
function mark(i, visited, c)
{
if (visited[i] > 0)
{
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
}
visited[i] = c;
// Increase the count
if (c == 1)
c_A++;
else
c_B++;
// Dfs for all its unvisited
// adjacent nodes
for(let j = 0;
j < graph[i].length; j++)
if (visited[graph[i][j]] > 0)
mark(graph[i][j], visited, c);
}
// Function to find the winner
// among the players
function findWinner()
{
// Finds the path
find(1, -1);
let visited = new Array(n + 1);
for(let i = 0;
i < path.length; i++)
{
// Mark nodes visited by
// A as 1 and B as 2
if (i < Math.ceil(path.length / 2.0))
{
visited[path[i]] = 1;
c_A++;
}
else
{
visited[path[i]] = 2;
c_B++;
}
}
// Mark all the adjacent
// unvisited nodes
for(let i = 0;
i < path.length; i++)
mark(path[i], visited,
visited[path[i]]);
if (c_A > c_B)
document.write("A wins");
else if (c_A < c_B)
document.write("B wins");
else
document.write("Draw");
}
// Driver code
n = 7;
graph = new Array(n + 1);
for(let i = 0;
i < graph.length; i++)
graph[i] = [];
// Graph
graph[6].push(4);
graph[4].push(6);
graph[6].push(5);
graph[5].push(6);
graph[5].push(7);
graph[7].push(5);
graph[5].push(2);
graph[2].push(5);
graph[3].push(4);
graph[4].push(3);
graph[1].push(4);
graph[4].push(1);
findWinner();
// This code is contributed by patel2127
</script>
Producción:
A wins
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA