Dado un árbol con N Nodes que inicialmente no tienen color y una array color[] de tamaño N que representa el color de cada Node después de que se lleva a cabo el proceso de coloración. La tarea es colorear el árbol en los colores dados utilizando el menor número posible de pasos. En cada paso, se puede elegir un vértice v y un color x , y luego colorear todos los vértices en el subárbol de v (incluido el propio v) con el color x . Tenga en cuenta que la raíz es el vértice número 1.
Ejemplos:
Entrada: color[] = { 1, 1, 2, 1, 3, 1}
Resultado: 4
Colorea el subárbol con raíz en el Node 1 con el color 1.
Luego, todos los vértices tienen el color 1.
Ahora, colorea el subárbol con raíz en 3 con el color 2.
Finalmente, colorea los subárboles con raíz en 5 y 6 con los colores 3 y 1 respectivamente.
Entrada: color[] = { 1, 2, 3, 2, 2, 3}
Salida: 3
Enfoque: llame a una función DFS en el vértice 1 e inicialmente mantenga la respuesta como cero. Incremente la respuesta cada vez que haya una diferencia en los colores de los Nodes padre e hijo.
Consulte el siguiente código para una mejor comprensión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// To store the required answer
int ans = 0;
// To store the graph
vector<int> gr[100005];
// Function to add edges
void Add_Edge(int u, int v)
{
gr[u].push_back(v);
gr[v].push_back(u);
}
// Dfs function
void dfs(int child, int par, int color[])
{
// When there is difference in colors
if (color[child] != color[par])
ans++;
// For all it's child nodes
for (auto it : gr[child]) {
if (it == par)
continue;
dfs(it, child, color);
}
}
// Driver code
int main()
{
// Here zero is for parent of node 1
int color[] = { 0, 1, 2, 3, 2, 2, 3 };
// Adding edges in the graph
Add_Edge(1, 2);
Add_Edge(1, 3);
Add_Edge(2, 4);
Add_Edge(2, 5);
Add_Edge(3, 6);
// Dfs call
dfs(1, 0, color);
// Required answer
cout << ans;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// To store the required answer
static int ans = 0;
// To store the graph
static Vector<Vector<Integer>> gr = new Vector<Vector<Integer>>();
// Function to add edges
static void Add_Edge(int u, int v)
{
gr.get(u).add(v);
gr.get(v).add(u);
}
// Dfs function
static void dfs(int child, int par, int color[])
{
// When there is difference in colors
if (color[child] != color[par])
ans++;
// For all it's child nodes
for (int i = 0; i < gr.get(child).size(); i++)
{
if (gr.get(child).get(i) == par)
continue;
dfs(gr.get(child).get(i), child, color);
}
}
// Driver code
public static void main(String args[])
{
for(int i = 0; i <= 10; i++)
gr.add(new Vector<Integer>());
// Here zero is for parent of node 1
int color[] = { 0, 1, 2, 3, 2, 2, 3 };
// Adding edges in the graph
Add_Edge(1, 2);
Add_Edge(1, 3);
Add_Edge(2, 4);
Add_Edge(2, 5);
Add_Edge(3, 6);
// Dfs call
dfs(1, 0, color);
// Required answer
System.out.println( ans);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # To store the required answer ans = 0 # To store the graph gr = [[] for i in range(100005)] # Function to add edges def Add_Edge(u, v): gr[u].append(v) gr[v].append(u) # Dfs function def dfs(child, par, color): global ans # When there is difference in colors if (color[child] != color[par]): ans += 1 # For all it's child nodes for it in gr[child]: if (it == par): continue dfs(it, child, color) # Driver code # Here zero is for parent of node 1 color = [0, 1, 2, 3, 2, 2, 3] # Adding edges in the graph Add_Edge(1, 2) Add_Edge(1, 3) Add_Edge(2, 4) Add_Edge(2, 5) Add_Edge(3, 6) # Dfs call dfs(1, 0, color) # Required answer print(ans) # This code is contributed # by mohit kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// To store the required answer
static int ans = 0;
// To store the graph
static List<List<int>> gr = new List<List<int>>();
// Function to add edges
static void Add_Edge(int u, int v)
{
gr[u].Add(v);
gr[v].Add(u);
}
// Dfs function
static void dfs(int child, int par, int []color)
{
// When there is difference in colors
if (color[child] != color[par])
ans++;
// For all it's child nodes
for (int i = 0; i < gr[child].Count; i++)
{
if (gr[child][i] == par)
continue;
dfs(gr[child][i], child, color);
}
}
// Driver code
public static void Main(String []args)
{
for(int i = 0; i <= 10; i++)
gr.Add(new List<int>());
// Here zero is for parent of node 1
int []color = { 0, 1, 2, 3, 2, 2, 3 };
// Adding edges in the graph
Add_Edge(1, 2);
Add_Edge(1, 3);
Add_Edge(2, 4);
Add_Edge(2, 5);
Add_Edge(3, 6);
// Dfs call
dfs(1, 0, color);
// Required answer
Console.WriteLine( ans);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// To store the required answer
let ans = 0;
// To store the graph
let gr = [];
// Function to add edges
function Add_Edge(u,v)
{
gr[u].push(v);
gr[v].push(u);
}
// Dfs function
function dfs(child,par,color)
{
// When there is difference in colors
if (color[child] != color[par])
ans++;
// For all it's child nodes
for (let i = 0; i < gr[child].length; i++)
{
if (gr[child][i] == par)
continue;
dfs(gr[child][i], child, color);
}
}
// Driver code
for(let i = 0; i <= 10; i++)
gr.push([]);
// Here zero is for parent of node 1
let color = [ 0, 1, 2, 3, 2, 2, 3 ];
// Adding edges in the graph
Add_Edge(1, 2);
Add_Edge(1, 3);
Add_Edge(2, 4);
Add_Edge(2, 5);
Add_Edge(3, 6);
// Dfs call
dfs(1, 0, color);
// Required answer
document.write( ans);
// This code is contributed by unknown2108
</script>
3
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA