Dado un árbol N-ario que consta de N Nodes con valores de [0, N – 1] y dos arrays binarias initial[] y final[] de tamaño N tal que initial[i] representa el valor asignado al Node i , la tarea es encontrar el número mínimo de operaciones requeridas para convertir cada valor de los Nodes initial[i] a final[i] cambiando el valor del Node, sus nietos, y así sucesivamente de manera alterna hasta los Nodes hoja .
Ejemplos:
Entrada: N = 3, bordes = {{1, 2}, {1, 3}}, initial[] = {1, 1, 0}, final[] = {0, 1, 1}
1(1)
/ \
2(1) 3(0)
Salida: 2
Explicación:
Operación 1: Selecciona el Node 1 y cambia sus valores iniciales. Después de esta operación inicial[] = {0, 1, 0} y final[] = {0, 1, 1}.
Operación 2: elige el Node 3 y voltea sus valores iniciales. Después de esta operación inicial[] = {0, 1, 1} y final[] = {0, 1, 1}.
Por lo tanto, imprima 2 como el número mínimo de operaciones.Entrada: N = 1, bordes = [], inicial [] = {0}, final [] = {1}
Salida: 1
Enfoque: el problema dado se puede resolver realizando el DFS Traversal en el árbol dado y actualizando el valor de los Nodes en la array initial[] de manera alternativa. Siga los pasos a continuación para resolver este problema:
- Inicialice una variable, digamos total como 0 para almacenar el recuento de operaciones requeridas.
- Realice DFS Traversal mientras realiza el seguimiento de dos variables booleanas (inicialmente como false ) que solo cambiarán cuando ocurra un cambio y realice los siguientes pasos:
- Marque el Node actual como el Node visitado.
- Si el valor de Bitwise XOR del valor inicial del Node actual, el valor final del Node actual y la variable booleana actual no es cero, invierta la variable booleana actual e incremente el valor del total en 1 .
- Atraviese todos los elementos secundarios no visitados del Node actual y solicite recursivamente el DFS Traversal para el Node secundario .
- Después de completar los pasos anteriores, imprima el valor del total como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
// Function to add an edges in graph
void addEdges(vector<int> adj[],
int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Function to perform the DFS of graph
// recursively from a given vertex u
void DFSUtil(int u, vector<int> adj[],
vector<bool>& visited,
bool foo, bool foo1,
int initial[], int final[],
int& ans)
{
visited[u] = true;
// Check for the condition for the
// flipping of node's initial value
if ((initial[u - 1] ^ foo)
^ final[u - 1]
== true) {
ans++;
foo ^= 1;
}
// Traverse all the children of the
// current source node u
for (int i = 0;
i < adj[u].size(); i++) {
// Swap foo and foo1 signifies
// there is change of level
if (visited[adj[u][i]] == false)
DFSUtil(adj[u][i], adj,
visited, foo1, foo,
initial, final, ans);
}
}
// Function to perform the DFSUtil()
// for all the unvisited vertices
int DFS(vector<int> adj[], int V,
int initial[], int final[])
{
int total = 0;
vector<bool> visited(V, false);
// Traverse the given set of nodes
for (int u = 1; u <= 1; u++) {
// If the current node is
// unvisited
if (visited[u] == false)
DFSUtil(u, adj, visited,
0, 0, initial,
final, total);
}
// Print the number of operations
cout << total;
}
// Function to count the number of
// flips required to change initial
// node values to final node value
void countOperations(int N, int initial[],
int final[],
int Edges[][2])
{
// Create adjacency list
vector<int> adj[N + 1];
// Add the given edges
for (int i = 0; i < N - 1; i++) {
addEdges(adj, Edges[i][0],
Edges[i][1]);
}
// DFS Traversal
DFS(adj, N + 1, initial, final);
}
// Driver Code
int main()
{
int N = 3;
int Edges[][2] = { { 1, 2 }, { 1, 3 } };
int initial[] = { 1, 1, 0 };
int final[] = { 0, 1, 1 };
countOperations(N, initial, final,
Edges);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Create adjacency list
static int N = 3;
static Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>();
static Vector<Boolean> visited;
static int ans;
// Function to add an edges in graph
static void addEdges(int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// Function to perform the DFS of graph
// recursively from a given vertex u
static void DFSUtil(int u, boolean foo, boolean foo1, boolean[] initial, boolean[] finall)
{
visited.set(u, true);
// Check for the condition for the
// flipping of node's initial value
if ((initial[u - 1] ^ foo)
^ finall[u - 1]
== true) {
ans+=1;
foo ^= true;
}
// Traverse all the children of the
// current source node u
for (int i = 0;
i < adj.get(u).size(); i++) {
// Swap foo and foo1 signifies
// there is change of level
if (visited.get(adj.get(u).get(i)) == false)
DFSUtil(adj.get(u).get(i), foo1, foo,
initial, finall);
}
}
// Function to perform the DFSUtil()
// for all the unvisited vertices
static void DFS(int V, boolean[] initial, boolean[] finall)
{
ans = 0;
visited = new Vector<Boolean>();
for(int i = 0; i < V; i++)
{
visited.add(false);
}
// Traverse the given set of nodes
for (int u = 1; u <= 1; u++) {
// If the current node is
// unvisited
if (visited.get(u) == false)
DFSUtil(u, false, false, initial, finall);
}
// Print the number of operations
System.out.print(ans);
}
// Function to count the number of
// flips required to change initial
// node values to final node value
static void countOperations(int N, boolean[] initial, boolean[] finall, int[][] Edges)
{
// Add the given edges
for (int i = 0; i < N - 1; i++) {
addEdges(Edges[i][0], Edges[i][1]);
}
// DFS Traversal
DFS(N + 1, initial, finall);
}
// Driver code
public static void main(String[] args) {
for(int i = 0; i < N + 1; i++)
{
adj.add(new Vector<Integer>());
}
int[][] Edges = { {1, 2}, {1, 3} };
boolean[] initial = { true, true, false };
boolean[] finall = { false, true, true};
countOperations(N, initial, finall, Edges);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program for the above approach # Create adjacency list N = 3 adj = [] for i in range(N + 1): adj.append([]) visited = [] ans = 0 # Function to add an edges in graph def addEdges(u, v): global adj adj[u].append(v) adj[v].append(u) # Function to perform the DFS of graph # recursively from a given vertex u def DFSUtil(u, foo, foo1, initial, finall): global visited, ans, adj visited[u] = True # Check for the condition for the # flipping of node's initial value if ((initial[u - 1] ^ foo) ^ finall[u - 1] == True): ans+=1 foo ^= True # Traverse all the children of the # current source node u for i in range(len(adj[u])): # Swap foo and foo1 signifies # there is change of level if (visited[adj[u][i]] == False): DFSUtil(adj[u][i], foo1, foo, initial, finall) # Function to perform the DFSUtil() # for all the unvisited vertices def DFS(V, initial, finall): global ans, visited ans = 0 visited = [False]*V # Traverse the given set of nodes for u in range(1, 2): # If the current node is # unvisited if (visited[u] == False): DFSUtil(u, 0, 0, initial, finall) # Print the number of operations print(ans) # Function to count the number of # flips required to change initial # node values to final node value def countOperations(N, initial, finall, Edges): # Add the given edges for i in range(N - 1): addEdges(Edges[i][0], Edges[i][1]) # DFS Traversal DFS(N + 1, initial, finall) Edges = [ [ 1, 2 ], [ 1, 3 ] ] initial = [ True, True, False ] finall = [ False, True, True] countOperations(N, initial, finall, Edges) # This code is contributed by rameshtravel07.
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
// Create adjacency list
static int N = 3;
static List<List<int>> adj = new List<List<int>>();
static List<bool> visited;
static int ans;
// Function to add an edges in graph
static void addEdges(int u, int v)
{
adj[u].Add(v);
adj[v].Add(u);
}
// Function to perform the DFS of graph
// recursively from a given vertex u
static void DFSUtil(int u, bool foo, bool foo1, bool[] initial, bool[] finall)
{
visited[u] = true;
// Check for the condition for the
// flipping of node's initial value
if ((initial[u - 1] ^ foo)
^ finall[u - 1]
== true) {
ans+=1;
foo ^= true;
}
// Traverse all the children of the
// current source node u
for (int i = 0;
i < adj[u].Count; i++) {
// Swap foo and foo1 signifies
// there is change of level
if (visited[adj[u][i]] == false)
DFSUtil(adj[u][i], foo1, foo,
initial, finall);
}
}
// Function to perform the DFSUtil()
// for all the unvisited vertices
static void DFS(int V, bool[] initial, bool[] finall)
{
ans = 0;
visited = new List<bool>();
for(int i = 0; i < V; i++)
{
visited.Add(false);
}
// Traverse the given set of nodes
for (int u = 1; u <= 1; u++) {
// If the current node is
// unvisited
if (visited[u] == false)
DFSUtil(u, false, false, initial, finall);
}
// Print the number of operations
Console.Write(ans);
}
// Function to count the number of
// flips required to change initial
// node values to final node value
static void countOperations(int N, bool[] initial, bool[] finall, int[,] Edges)
{
// Add the given edges
for (int i = 0; i < N - 1; i++) {
addEdges(Edges[i,0], Edges[i,1]);
}
// DFS Traversal
DFS(N + 1, initial, finall);
}
static void Main() {
for(int i = 0; i < N + 1; i++)
{
adj.Add(new List<int>());
}
int[,] Edges = { {1, 2}, {1, 3} };
bool[] initial = { true, true, false };
bool[] finall = { false, true, true};
countOperations(N, initial, finall, Edges);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program for the above approach
// Create adjacency list
let N = 3;
let adj = [];
for(let i = 0; i < N + 1; i++)
{
adj.push([]);
}
let visited;
let ans;
// Function to add an edges in graph
function addEdges(u, v)
{
adj[u].push(v);
adj[v].push(u);
}
// Function to perform the DFS of graph
// recursively from a given vertex u
function DFSUtil(u, foo, foo1, initial, finall)
{
visited[u] = true;
// Check for the condition for the
// flipping of node's initial value
if ((initial[u - 1] ^ foo)
^ finall[u - 1]
== true) {
ans+=1;
foo ^= true;
}
// Traverse all the children of the
// current source node u
for (let i = 0;
i < adj[u].length; i++) {
// Swap foo and foo1 signifies
// there is change of level
if (visited[adj[u][i]] == false)
DFSUtil(adj[u][i], foo1, foo,
initial, finall);
}
}
// Function to perform the DFSUtil()
// for all the unvisited vertices
function DFS(V, initial, finall)
{
ans = 0;
visited = new Array(V);
visited.fill(false);
// Traverse the given set of nodes
for (let u = 1; u <= 1; u++) {
// If the current node is
// unvisited
if (visited[u] == false)
DFSUtil(u, 0, 0, initial, finall);
}
// Print the number of operations
document.write(ans);
}
// Function to count the number of
// flips required to change initial
// node values to final node value
function countOperations(N, initial, finall, Edges)
{
// Add the given edges
for (let i = 0; i < N - 1; i++) {
addEdges(Edges[i][0], Edges[i][1]);
}
// DFS Traversal
DFS(N + 1, initial, finall);
}
let Edges = [ [ 1, 2 ], [ 1, 3 ] ];
let initial = [ true, true, false ];
let finall = [ false, true, true];
countOperations(N, initial, finall, Edges);
// This code iscontributed by decode2207.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA