Check which player visits more number of Nodes
Given a tree with N nodes. Two players A and B start from node 1 and node N respectively. A can visit all the adjacent nodes to the nodes already visited by A but can not visit any nodes which is already visited by B and similarly for B also.
The player who visits more cities win. Find the player who wins if they both play optimally.
Examples:
Input:
Output: A wins
Approach: The optimal solution is that both the Player starts visiting the nodes which lie in the path connecting node 1 and node N. This is because one player cannot visit the nodes already visited by another player so each player will try to limit the number of nodes that can be visited by another player. Then it will be easy to count the number of nodes that can be visited by each player and find out the winner.
The DFS will be used to find out the path between two nodes and mark them one by one like 1 or 2, 1 for A and 2 for B and then mark all the adjacent unvisited nodes with the respective value and then calculate the count of nodes of A and B.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Vector to store Treevector<vector<int> > graph;// To check if there// is path or notint found = 0, n;// Path and temporary vectorvector<int> path, temp;// Count of A and Bint c_A = 0, c_B = 0;// Function to find the path connecting 1 to nvoid 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 nodesvoid 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 playersvoid 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 codeint 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 approachimport java.util.*;class GFG{// Vector to store Treestatic Vector<Integer> []graph;// To check if there// is path or notstatic int found = 0, n;// Path and temporary vectorstatic Vector<Integer> path = new Vector<>();static Vector<Integer> temp = new Vector<>();// Count of A and Bstatic int c_A = 0, c_B = 0;// Function to find the path // connecting 1 to nstatic 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 nodesstatic 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 playersstatic 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 approachfrom math import ceil, floor# Vector to store Treegraph = [[] for i in range(1000)]# To check if there# is path or notfound = 0n = 0# Path and temporary vectorpath = []temp = []# Count of A and Bc_A = 0c_B = 0# Function to find the path connecting 1 to ndef 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 nodesdef 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 playersdef 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 coden = 7# Graphgraph[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 approachusing System;using System.Collections.Generic;class GFG{// List to store Treestatic List<int> []graph;// To check if there// is path or notstatic int found = 0, n;// Path and temporary vectorstatic List<int> path = new List<int>();static List<int> temp = new List<int>();// Count of A and Bstatic int c_A = 0, c_B = 0;// Function to find the path // connecting 1 to nstatic 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 nodesstatic 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 playersstatic 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 codepublic 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 Treelet graph;// To check if there// is path or notlet found = 0, n;// Path and temporary vectorlet path = [];let temp = [];// Count of A and Blet c_A = 0, c_B = 0;// Function to find the path// connecting 1 to nfunction 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 nodesfunction 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 playersfunction 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 coden = 7;graph = new Array(n + 1);for(let i = 0; i < graph.length; i++) graph[i] = [];// Graphgraph[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> |
Output:
A wins
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
