Dado un árbol binario con N Nodes numerados [1, N] , la tarea es encontrar el tamaño del conjunto Dominante más pequeño de ese árbol.
Se dice que un conjunto de Nodes es un Node dominante si cada Node en el árbol binario que no está presente en el conjunto es un hijo/padre inmediato de cualquier Node en ese conjunto.
Ejemplos:
Input:
1
/
2
/ \
4 3
/
5
/ \
6 7
/ \ \
8 9 10
Output: 3
Explanation:
Smallest dominating set is {2, 6, 7}
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
Output: 4
Explanation:
One of the smallest
dominating set = {2, 3, 6, 4}
Enfoque:
para resolver este problema, utilizamos un enfoque de programación dinámica al definir los siguientes dos estados para cada Node:
- El primer estado obligatorio nos dice si es obligatorio elegir el Node del conjunto o no.
- El segundo estado cubierto nos dice si el padre/hijo del Node está en el conjunto o no.
Si es obligatorio elegir el Node, lo elegimos y marcamos sus hijos como cubiertos. De lo contrario, tenemos la opción de elegirlo o rechazarlo y luego actualizar sus elementos secundarios como cubiertos o no según corresponda. Verifique los estados de cada Node y encuentre el tamaño requerido del conjunto en consecuencia.
El siguiente código es la implementación del enfoque anterior:
C++
/* C++ program to find the size of the
minimum dominating set of the tree */
#include <bits/stdc++.h>
using namespace std;
#define N 1005
// Definition of a tree node
struct Node {
int data;
Node *left, *right;
};
/* Helper function that allocates a
new node */
Node* newNode(int data)
{
Node* node = new Node();
node->data = data;
node->left = node->right = NULL;
return node;
}
// DP array to precompute
// and store the results
int dp[N][5][5];
// minDominatingSettion to return the size of
// the minimum dominating set of the array
int minDominatingSet(Node* root, int covered,
int compulsory)
{
// Base case
if (!root)
return 0;
// Setting the compulsory value if needed
if (!root->left and !root->right and !covered)
compulsory = true;
// Check if the answer is already computed
if (dp[root->data][covered][compulsory] != -1)
return dp[root->data][covered][compulsory];
// If it is compulsory to select
// the node
if (compulsory) {
// Choose the node and set its children as covered
return dp[root->data]
[covered]
[compulsory]
= 1
+ minDominatingSet(
root->left, 1, 0)
+ minDominatingSet(
root->right, 1, 0);
}
// If it is covered
if (covered) {
return dp[root->data]
[covered]
[compulsory]
= min(
1
+ minDominatingSet(
root->left, 1, 0)
+ minDominatingSet(
root->right, 1, 0),
minDominatingSet(
root->left, 0, 0)
+ minDominatingSet(
root->right, 0, 0));
}
// If the current node is neither covered nor
// needs to be selected compulsorily
int ans = 1
+ minDominatingSet(
root->left, 1, 0)
+ minDominatingSet(
root->right, 1, 0);
if (root->left) {
ans = min(ans,
minDominatingSet(
root->left, 0, 1)
+ minDominatingSet(
root->right, 0, 0));
}
if (root->right) {
ans = min(ans,
minDominatingSet(
root->left, 0, 0)
+ minDominatingSet(
root->right, 0, 1));
}
// Store the result
return dp[root->data]
[covered]
[compulsory]
= ans;
}
// Driver code
signed main()
{
// initialising the DP array
memset(dp, -1, sizeof(dp));
// Constructing the tree
Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->left->left->left = newNode(5);
root->left->left->left->left = newNode(6);
root->left->left->left->right = newNode(7);
root->left->left->left->right->right = newNode(10);
root->left->left->left->left->left = newNode(8);
root->left->left->left->left->right = newNode(9);
cout << minDominatingSet(root, 0, 0) << endl;
return 0;
}
Java
// Java program to find the size of the
//minimum dominating set of the tree
import java.util.*;
class GFG{
static final int N = 1005;
// Definition of a tree node
static class Node
{
int data;
Node left, right;
};
// Helper function that allocates a
// new node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// DP array to precompute
// and store the results
static int [][][]dp = new int[N][5][5];
// minDominatingSettion to return the size of
// the minimum dominating set of the array
static int minDominatingSet(Node root,
int covered,
int compulsory)
{
// Base case
if (root == null)
return 0;
// Setting the compulsory value if needed
if (root.left != null &&
root.right != null &&
covered > 0)
compulsory = 1;
// Check if the answer is already computed
if (dp[root.data][covered][compulsory] != -1)
return dp[root.data][covered][compulsory];
// If it is compulsory to select
// the node
if (compulsory > 0)
{
// Choose the node and set its
// children as covered
return dp[root.data][covered][compulsory] = 1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
}
// If it is covered
if (covered > 0)
{
return dp[root.data][covered]
[compulsory] = Math.min(1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0),
minDominatingSet(root.left, 0, 0)+
minDominatingSet(root.right, 0, 0));
}
// If the current node is neither covered nor
// needs to be selected compulsorily
int ans = 1 + minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
if (root.left != null)
{
ans = Math.min(ans,
minDominatingSet(root.left, 0, 1) +
minDominatingSet(root.right, 0, 0));
}
if (root.right != null)
{
ans = Math.min(ans,
minDominatingSet(root.left, 0, 0) +
minDominatingSet(root.right, 0, 1));
}
// Store the result
return dp[root.data][covered][compulsory] = ans;
}
// Driver code
public static void main(String[] args)
{
// Initialising the DP array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 5; j++)
{
for(int l = 0; l < 5; l++)
dp[i][j][l] = -1;
}
}
// Constructing the tree
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.left.left.left = newNode(5);
root.left.left.left.left = newNode(6);
root.left.left.left.right = newNode(7);
root.left.left.left.right.right = newNode(10);
root.left.left.left.left.left = newNode(8);
root.left.left.left.left.right = newNode(9);
System.out.print(minDominatingSet(
root, 0, 0) + "\n");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to find the size of the # minimum dominating set of the tree */ N = 1005 # Definition of a tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Helper function that allocates a # new node def newNode(data): node = Node(data) return node # DP array to precompute # and store the results dp = [[[-1 for i in range(5)] for j in range(5)] for k in range(N)]; # minDominatingSettion to return the size of # the minimum dominating set of the array def minDominatingSet(root, covered, compulsory): # Base case if (not root): return 0; # Setting the compulsory value if needed if (not root.left and not root.right and not covered): compulsory = True; # Check if the answer is already computed if (dp[root.data][covered][compulsory] != -1): return dp[root.data][covered][compulsory]; # If it is compulsory to select # the node if (compulsory): dp[root.data][covered][compulsory] = 1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0); # Choose the node and set its children as covered return dp[root.data][covered][compulsory] # If it is covered if (covered): dp[root.data][covered][compulsory] = min(1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0),minDominatingSet(root.left, 0, 0)+ minDominatingSet(root.right, 0, 0)); return dp[root.data][covered][compulsory] # If the current node is neither covered nor # needs to be selected compulsorily ans = 1 + minDominatingSet(root.left, 1, 0) + minDominatingSet(root.right, 1, 0); if (root.left): ans = min(ans, minDominatingSet(root.left, 0, 1) + minDominatingSet(root.right, 0, 0)); if (root.right): ans = min(ans, minDominatingSet( root.left, 0, 0) + minDominatingSet(root.right, 0, 1)); # Store the result dp[root.data][covered][compulsory]= ans; return ans # Driver code if __name__=='__main__': # Constructing the tree root = newNode(1); root.left = newNode(2); root.left.left = newNode(3); root.left.right = newNode(4); root.left.left.left = newNode(5); root.left.left.left.left = newNode(6); root.left.left.left.right = newNode(7); root.left.left.left.right.right = newNode(10); root.left.left.left.left.left = newNode(8); root.left.left.left.left.right = newNode(9); print(minDominatingSet(root, 0, 0)) # This code is contributed by rutvik_56
C#
// C# program to find the size of the
//minimum dominating set of the tree
using System;
class GFG{
static readonly int N = 1005;
// Definition of a tree node
public class Node
{
public
int data;
public
Node left, right;
};
// Helper function that allocates a
// new node
public static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// DP array to precompute
// and store the results
static int [,,]dp = new int[N, 5, 5];
// minDominatingSettion to return the size of
// the minimum dominating set of the array
static int minDominatingSet(Node root,
int covered,
int compulsory)
{
// Base case
if (root == null)
return 0;
// Setting the compulsory value if needed
if (root.left != null &&
root.right != null &&
covered > 0)
compulsory = 1;
// Check if the answer is already computed
if (dp[root.data, covered, compulsory] != -1)
return dp[root.data, covered, compulsory];
// If it is compulsory to select
// the node
if (compulsory > 0)
{
// Choose the node and set its
// children as covered
return dp[root.data, covered, compulsory] = 1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
}
// If it is covered
if (covered > 0)
{
return dp[root.data, covered, compulsory] = Math.Min(1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0),
minDominatingSet(root.left, 0, 0)+
minDominatingSet(root.right, 0, 0));
}
// If the current node is neither covered nor
// needs to be selected compulsorily
int ans = 1 + minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
if (root.left != null)
{
ans = Math.Min(ans,
minDominatingSet(root.left, 0, 1) +
minDominatingSet(root.right, 0, 0));
}
if (root.right != null)
{
ans = Math.Min(ans,
minDominatingSet(root.left, 0, 0) +
minDominatingSet(root.right, 0, 1));
}
// Store the result
return dp[root.data, covered, compulsory] = ans;
}
// Driver code
public static void Main(String[] args)
{
// Initialising the DP array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 5; j++)
{
for(int l = 0; l < 5; l++)
dp[i, j, l] = -1;
}
}
// Constructing the tree
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.left.left.left = newNode(5);
root.left.left.left.left = newNode(6);
root.left.left.left.right = newNode(7);
root.left.left.left.right.right = newNode(10);
root.left.left.left.left.left = newNode(8);
root.left.left.left.left.right = newNode(9);
Console.Write(minDominatingSet
root, 0, 0) + "\n");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program to find the size of the
//minimum dominating set of the tree
let N = 1005;
// Definition of a tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Helper function that allocates a
// new node
function newNode(data)
{
let node = new Node(data);
return node;
}
// DP array to precompute
// and store the results
let dp = new Array(N);
// minDominatingSettion to return the size of
// the minimum dominating set of the array
function minDominatingSet(root, covered, compulsory)
{
// Base case
if (root == null)
return 0;
// Setting the compulsory value if needed
if (root.left != null &&
root.right != null &&
covered > 0)
compulsory = 1;
// Check if the answer is already computed
if (dp[root.data][covered][compulsory] != -1)
return dp[root.data][covered][compulsory];
// If it is compulsory to select
// the node
if (compulsory > 0)
{
// Choose the node and set its
// children as covered
return dp[root.data][covered][compulsory] = 1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
}
// If it is covered
if (covered > 0)
{
return dp[root.data][covered]
[compulsory] = Math.min(1 +
minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0),
minDominatingSet(root.left, 0, 0)+
minDominatingSet(root.right, 0, 0));
}
// If the current node is neither covered nor
// needs to be selected compulsorily
let ans = 1 + minDominatingSet(root.left, 1, 0) +
minDominatingSet(root.right, 1, 0);
if (root.left != null)
{
ans = Math.min(ans,
minDominatingSet(root.left, 0, 1) +
minDominatingSet(root.right, 0, 0));
}
if (root.right != null)
{
ans = Math.min(ans,
minDominatingSet(root.left, 0, 0) +
minDominatingSet(root.right, 0, 1));
}
// Store the result
dp[root.data][covered][compulsory] = ans;
return dp[root.data][covered][compulsory];
}
// Initialising the DP array
for(let i = 0; i < N; i++)
{
dp[i] = new Array(5);
for(let j = 0; j < 5; j++)
{
dp[i][j] = new Array(5);
for(let l = 0; l < 5; l++)
dp[i][j][l] = -1;
}
}
// Constructing the tree
let root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.left.left.left = newNode(5);
root.left.left.left.left = newNode(6);
root.left.left.left.right = newNode(7);
root.left.left.left.right.right = newNode(10);
root.left.left.left.left.left = newNode(8);
root.left.left.left.left.right = newNode(9);
document.write(minDominatingSet(root, 0, 0));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Shrey Tanna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA