Dado un grafo dirigido G que consta de N Nodes y N-1 aristas, y un entero positivo K, e inicialmente todos los Nodes del grafo son rojos excepto K, que es negro, la tarea es contar el número de diferentes posibles gráficos formados al cambiar el color de cualquier Node de color rojo a negro, solo si su padre es de color negro, cualquier número de veces.
Ejemplos:
Entrada: N = 5, K = 1, Edges[] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}} Salida: 10 Explicación: cuando el Node 2
es rojo
,
entonces no podemos cambiar el color de 4 y 5 porque su padre (2) no es negro. Por lo tanto, solo hay una forma posible de colorear.1(B)
/ \
2(R) 3(R)
/ \
4(R) 5(R)
Pero cuando 2 es negro, entonces podemos cambiar el color de 4 y 5 (4 y 5 son independientes entre sí) de 2 formas posibles, cada uno (rojo-negro) porque su padre (2) es negro.
El Node 3 nuevamente se puede colorear de 2 maneras diferentes. Por lo tanto, el número total de formas de colorear es (5*2 = 10). Por lo tanto, hay un total de 10 gráficos posibles diferentes.
Entrada: N = 3, K = 2, Bordes[] = {{1, 2}, {1, 3}}
Salida: 1
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
- El gráfico dirigido dado se puede tratar como un árbol con raíz en el Node K. Y el número de diferentes gráficos posibles es el mismo que el número de formas de colorear el gráfico en consecuencia.
- Los hijos de cualquier Node pueden ser de color negro solo si el Node principal es de color negro. Por lo tanto, todos los Nodes desde el K hasta el Node actual deben ser de color negro.
- Por lo tanto, la idea es realizar un recorrido DFS desde K y, para cada Node, colorear el Node actual de negro o dejarlo como está. Luego, atravesar los subárboles solo si el Node actual está coloreado de negro.
- Si hay 3 hijos del Node actual U , y X, Y, Z es el número de formas de colorear los subárboles de los hijos del Node U. Entonces el número total de formas de colorear el subárbol actual es (X*Y* Z+1). El Node K no se puede colorear, por lo que no se agrega 1 al Node K.
Siga los pasos a continuación para resolver el problema:
- Forme una lista de adyacencia a partir de los bordes dados del gráfico y guárdela en una variable, digamos gráfico
- Defina una función recursiva , digamos, numOfGraph(U) donde U es el Node actual:
- Si el Node U es la hoja, devuelve 2 . Como el Node puede ser de color negro o rojo.
- Inicialice una variable, digamos cnt , que almacene la cantidad de formas de colorear el gráfico.
- Iterar sobre el Node conectado con el Node actual U, usando la variable i , y realizar los siguientes pasos:
- Actualice el valor de cnt a cnt*NumberOfGraph(i) llamando recursivamente a la función para el Node secundario i .
- Después de los pasos anteriores, devuelva el valor de cnt+1.
- Finalmente, llame a la función DFS desde el Node K , es decir, numOfGraph(K) , e imprima el valor devuelto como respuesta.
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;
// Class to represents a directed graph
// using adjacency list representation
// Constructor
int V;
vector<int> graph[100];
// Function to add an edge in an directed
// graph
void addEdge(int u, int v)
{
graph[u].push_back(v);
}
// Function to count number of
// possible graphs with given
// coloring
int numOfGraph(int u)
{
// If node is leaf node
if (graph[u].size() == 0)
return 2;
// Stores the number of ways to
// color the subtree of node u
int cnt = 1;
// Traverse over the children of
// node u
for(int i:graph[u])
{
// Multiply number of possible ways
// to color the subtree
cnt *= numOfGraph(i);
}
// Return cnt
return cnt + 1;
}
// Driver code
int main()
{
// Create a graph
V = 5;
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Node initially in black
int K = 1;
// Function Call
cout << (numOfGraph(K) - 1);
return 0;
}
// This code is contributed by Mohit kumar
Java
// Java program for above approach
import java.util.*;
class Graph{
// Function to add an edge in an directed
// graph
static void addEdge(int u, int v,
ArrayList<ArrayList<Integer>> graph)
{
graph.get(u).add(v);
}
// Function to count number of
// possible graphs with given
// coloring
static int numOfGraph(int u,
ArrayList<ArrayList<Integer>> graph)
{
// If node is leaf node
if (graph.get(u).size() == 0)
return 2;
// Stores the number of ways to
// color the subtree of node u
int cnt = 1;
// Traverse over the children of
// node u
for(int i:graph.get(u))
{
// Multiply number of possible ways
// to color the subtree
cnt *= numOfGraph(i,graph);
}
// Return cnt
return cnt + 1;
}
// Driver code
public static void main(String[] args)
{
// Represents a directed graph
// using adjacency list representation
int V;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
// Create a graph
V = 5;
for(int i = 0; i <= V; i++)
graph.add(new ArrayList<>());
addEdge(1, 2, graph);
addEdge(1, 3, graph);
addEdge(2, 4, graph);
addEdge(2, 5, graph);
// Node initially in black
int K = 1;
// Function Call
System.out.println((numOfGraph(K, graph) - 1));
}
}
// This code is contributed by hritikrommie
Python3
# Python3 program for the above approach # Import library for create defaultdict from collections import defaultdict # Class to represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self, vertices): self.V = vertices self.graph = defaultdict(list) # Function to add an edge in an directed # graph def addEdge(self, u, v): self.graph[u].append(v) # Function to count number of # possible graphs with given # coloring def numOfGraph(self, u): # If node is leaf node if u not in self.graph: return 2 # Stores the number of ways to # color the subtree of node u cnt = 1 # Traverse over the children of # node u for i in self.graph[u]: # Multiply number of possible ways # to color the subtree cnt *= self.numOfGraph(i) # Return cnt return cnt + 1 # Driver code if __name__ == "__main__": # Create a graph g = Graph(5) g.addEdge(1, 2) g.addEdge(1, 3) g.addEdge(2, 4) g.addEdge(2, 5) # Node initially in black K = 1 # Function Call print(g.numOfGraph(K)-1)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class Graph{
static int V;
//Adjacency Lists
static LinkedList<int>[] graph;
// Function to add an edge in an directed
// graph
public void addEdge(int u, int v)
{
graph[u].AddLast(v);
}
public Graph(int v)
{
graph = new LinkedList<int>[v];
for(int i = 0; i <= V; i++)
{
graph[i] = new LinkedList<int>();
}
}
// Function to count number of
// possible graphs with given
// coloring
static int numOfGraph(int u)
{
// If node is leaf node
if (graph[u].Count == 0)
return 2;
// Stores the number of ways to
// color the subtree of node u
int cnt = 1;
// Traverse over the children of
// node u
foreach (var i in graph[u])
{
// Multiply number of possible ways
// to color the subtree
cnt *= numOfGraph(i);
}
// Return cnt
return cnt + 1;
}
// Driver code
static public void Main (){
V = 5;
// Create a graph
Graph g = new Graph(100);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
// Node initially in black
int K = 1;
// Function Call
Console.WriteLine(numOfGraph(K) - 1);
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Javascript program for the above approach
let V;
//Adjacency Lists
let graph = new Array(100);
for(let i = 0; i < 100; i++)
{
graph[i] = []
}
// Function to add an edge in an directed
// graph
function addEdge(u, v)
{
graph[u].push(v);
}
// Function to count number of
// possible graphs with given
// coloring
function numOfGraph(u)
{
// If node is leaf node
if (graph[u].length == 0)
return 2;
// Stores the number of ways to
// color the subtree of node u
let cnt = 1;
// Traverse over the children of
// node u
for(let i = 0; i < graph[u].length; i++)
{
// Multiply number of possible ways
// to color the subtree
cnt *= numOfGraph(graph[u][i]);
}
// Return cnt
return cnt + 1;
}
// Create a graph
V = 5;
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Node initially in black
let K = 1;
// Function Call
document.write(numOfGraph(K) - 1);
// This code is contributed by decode2207.
</script>
Producción
10
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA