Dado un árbol con N Nodes valores de 1 a N y N – 1 aristas. La tarea es encontrar la coincidencia máxima en el árbol dado.
Una coincidencia en un árbol es una colección de aristas tal que ningún par de aristas comparte un Node común. La coincidencia con la mayoría de los bordes se conoce como coincidencia máxima .
Ejemplos:
Entrada: A continuación se muestra el gráfico dado:
Salida: 3
Explicación:
Conjunto de aristas en el gráfico anterior para coincidencia máxima:
(4, 5), (1, 2), (7, 8)Entrada: A continuación se muestra el gráfico dado:
Salida: 3
Explicación:
Conjunto de aristas en el gráfico anterior para coincidencia máxima:
(4, 5), (2, 3), (1, 7)
Enfoque: este problema se puede resolver usando el enfoque codicioso y la idea es usar el recorrido posterior al orden en el árbol y comenzar con los bordes de las hojas y subir el orden. A continuación se muestran los pasos:
- Realice DFS Traversal en el árbol dado con el Node raíz 1 y haga que el padre sea 0 y pase los Nodes actuales como padre del Node en el DFS transversal recursivo.
- Mientras realiza el recorrido, para cada Node U y su Node principal P , si estos Nodes no están visitados, marque estos Nodes como visitados e incremente el recuento máximo de coincidencias en 1.
- Imprima el recuento de una coincidencia máxima en el paso anterior después de DFS Traversal.
El algoritmo Greedy consiste en tomar repetidamente cualquier borde de hoja.
TreeMatch(F:forest)
M <- []
while F nonempty do {
select any leaf-edge e
M <- M + [e]
F <- F - both ends of e
}
¿Por qué el algoritmo codicioso funciona correctamente?
Supongamos que E es un borde de hoja y consideremos cualquier coincidencia máxima N . Supongamos que N no contiene E. Entonces, si sumamos E a N , ahora solo un vértice tiene dos aristas incidentes con él. Entonces podemos eliminar uno de los bordes de N y lograr una coincidencia máxima que contenga E .
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;
#define N 10000
// Adjacency list to store edges
vector<int> adj[N];
int used[N];
int max_matching;
// Add an edge between U and V in tree
void AddEdge(int u, int v)
{
// Edge from u to v
adj[u].push_back(v);
// Edge from V to U
adj[v].push_back(u);
}
// Function that finds the maximum
// matching of the DFS
void Matching_dfs(int u, int p)
{
for (int i = 0;
i < adj[u].size(); i++) {
// Go further as we are not
// allowed to go towards
// its parent
if (adj[u][i] != p) {
Matching_dfs(adj[u][i], u);
}
}
// If U and its parent P is
// not taken then we must
// take &mark them as taken
if (!used[u] and !used[p] and p != 0) {
// Increment size of edge set
max_matching++;
used[u] = used[p] = 1;
}
}
// Function to find the maximum
// matching in a graph
void maxMatching()
{
// Taking 1 as a root of the tree
Matching_dfs(1, 0);
// Print maximum Matching
cout << max_matching << "\n";
}
// Driver Code
int main()
{
int n = 5;
// Joining edge between
// two nodes in tree
AddEdge(1, 2);
AddEdge(1, 3);
AddEdge(3, 4);
AddEdge(3, 5);
// Function Call
maxMatching();
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int N = 10000;
// Adjacency list to store edges
@SuppressWarnings("unchecked")
static Vector<Integer>[] adj = new Vector[N];
static int used[] = new int[N];
static int max_matching;
// Add an edge between U and V in tree
static void AddEdge(int u, int v)
{
// Edge from u to v
adj[u].add(v);
// Edge from V to U
adj[v].add(u);
}
// Function that finds the maximum
// matching of the DFS
static void Matching_dfs(int u, int p)
{
for(int i = 0; i < adj[u].size(); i++)
{
// Go further as we are not
// allowed to go towards
// its parent
if (adj[u].get(i) != p)
{
Matching_dfs(adj[u].get(i), u);
}
}
// If U and its parent P is
// not taken then we must
// take &mark them as taken
if (used[u] == 0 &&
used[p] == 0 && p != 0)
{
// Increment size of edge set
max_matching++;
used[u] = used[p] = 1;
}
}
// Function to find the maximum
// matching in a graph
static void maxMatching()
{
// Taking 1 as a root of the tree
Matching_dfs(1, 0);
// Print maximum Matching
System.out.print(max_matching + "\n");
}
// Driver Code
public static void main(String[] args)
{
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// Joining edge between
// two nodes in tree
AddEdge(1, 2);
AddEdge(1, 3);
AddEdge(3, 4);
AddEdge(3, 5);
// Function call
maxMatching();
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program for the above approach
N = 10000
# Adjacency list to store edges
adj = {}
used = [0 for i in range(N)]
max_matching = 0
# Add an edge between U and V in tree
def AddEdge(u, v):
if u not in adj:
adj[u] = []
if v not in adj:
adj[v] = []
# Edge from u to v
adj[u].append(v)
# Edge from V to U
adj[v].append(u)
# Function that finds the maximum
# matching of the DFS
def Matching_dfs(u, p):
global max_matching
for i in range(len(adj[u])):
# Go further as we are not
# allowed to go towards
# its parent
if (adj[u][i] != p):
Matching_dfs(adj[u][i], u)
# If U and its parent P is
# not taken then we must
# take &mark them as taken
if (not used[u] and not used[p] and p != 0):
# Increment size of edge set
max_matching += 1
used[u] = 1
used[p] = 1
# Function to find the maximum
# matching in a graph
def maxMatching():
# Taking 1 as a root of the tree
Matching_dfs(1, 0)
# Print maximum Matching
print(max_matching)
# Driver Code
n = 5
# Joining edge between
# two nodes in tree
AddEdge(1, 2)
AddEdge(1, 3)
AddEdge(3, 4)
AddEdge(3, 5)
# Function Call
maxMatching()
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int N = 10000;
// Adjacency list to store edges
static List<int>[] adj = new List<int>[N];
static int []used = new int[N];
static int max_matching;
// Add an edge between U and V in tree
static void AddEdge(int u, int v)
{
// Edge from u to v
adj[u].Add(v);
// Edge from V to U
adj[v].Add(u);
}
// Function that finds the maximum
// matching of the DFS
static void Matching_dfs(int u, int p)
{
for(int i = 0; i < adj[u].Count; i++)
{
// Go further as we are not
// allowed to go towards
// its parent
if (adj[u][i] != p)
{
Matching_dfs(adj[u][i], u);
}
}
// If U and its parent P is
// not taken then we must
// take &mark them as taken
if (used[u] == 0 &&
used[p] == 0 && p != 0)
{
// Increment size of edge set
max_matching++;
used[u] = used[p] = 1;
}
}
// Function to find the maximum
// matching in a graph
static void maxMatching()
{
// Taking 1 as a root of the tree
Matching_dfs(1, 0);
// Print maximum Matching
Console.Write(max_matching + "\n");
}
// Driver Code
public static void Main(String[] args)
{
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// Joining edge between
// two nodes in tree
AddEdge(1, 2);
AddEdge(1, 3);
AddEdge(3, 4);
AddEdge(3, 5);
// Function call
maxMatching();
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript Program to implement the above approach
let N = 10000;
// Adjacency list to store edges
let adj = new Array(N);
let used = new Array(N);
used.fill(0);
let max_matching = 0;
// Add an edge between U and V in tree
function AddEdge(u, v)
{
// Edge from u to v
adj[u].push(v);
// Edge from V to U
adj[v].push(u);
}
// Function that finds the maximum
// matching of the DFS
function Matching_dfs(u, p)
{
for(let i = 0; i < adj[u].length; i++)
{
// Go further as we are not
// allowed to go towards
// its parent
if (adj[u][i] != p)
{
Matching_dfs(adj[u][i], u);
}
}
// If U and its parent P is
// not taken then we must
// take &mark them as taken
if (used[u] == 0 &&
used[p] == 0 && p != 0)
{
// Increment size of edge set
max_matching++;
used[u] = used[p] = 1;
}
}
// Function to find the maximum
// matching in a graph
function maxMatching()
{
// Taking 1 as a root of the tree
Matching_dfs(1, 0);
// Print maximum Matching
document.write(max_matching + "</br>");
}
for(let i = 0; i < adj.length; i++)
adj[i] = [];
// Joining edge between
// two nodes in tree
AddEdge(1, 2);
AddEdge(1, 3);
AddEdge(3, 4);
AddEdge(3, 5);
// Function call
maxMatching();
</script>
2
Complejidad temporal: O(V + E), donde V es el número de aristas y E es el número de aristas.
Espacio Auxiliar: O(V)
Enfoque de SFD de abajo hacia arriba :
Otro enfoque intuitivo para resolver este problema es utilizar DFS de forma ascendente y devolver dos valores en cada nivel.
Coincidencia máxima incluido el Node actual
Coincidencia máxima excluyendo el Node actual
Haremos recursividad en los subárboles izquierdo y derecho y obtendremos estos valores para ambos. Luego podemos calcular nuevos valores para el nivel actual en función de estos valores.
Deje que left_included denote la coincidencia máxima, incluida la raíz del subárbol izquierdo, y que left_excluded denote la coincidencia máxima, excluyendo la raíz del subárbol izquierdo. Del mismo modo, para right_inclusive y right_excluded.
Si incluimos el Node actual en la coincidencia máxima, entonces tenemos que excluir uno de la raíz del subárbol izquierdo o la raíz del subárbol derecho. La inclusión de ambos provocará una superposición en el Node actual, lo que no está permitido. Al excluir la raíz del subárbol izquierdo o derecho, podemos aumentar la coincidencia máxima en 1 al incluir uno de los bordes de current_node -> raíz del subárbol izquierdo o current_node -> raíz del subárbol derecho.
Por lo tanto, la coincidencia máxima, incluido el Node actual, estará dada por
current_incluye = max(max(left_incluye, right_excluye) + 1, max(left_excluye, right_incluye) + 1)
Si excluimos el Node actual, podemos incluir la raíz del subárbol izquierdo y derecho. Como las coincidencias en los subárboles izquierdo y derecho son independientes entre sí, podemos obtener el valor máximo sumando ambas coincidencias.
Por lo tanto, la coincidencia máxima excluyendo el Node actual estará dada por
exclusión_actual = inclusión_izquierda + inclusión_derecha
Devolveremos estos dos valores desde el nivel de recursión actual a los niveles de recursión superiores. Después de que se complete la recursión, recibiremos dos valores, coincidencia máxima que incluye el Node raíz y coincidencia máxima que excluye el Node raíz.
El máximo de esos dos dará la máxima coincidencia en el árbol.
Python3
class Node: def __init__(self, key): self.left = None self.right = None self.val = key def max_matching_helper(root): if not root: return (0, 0) if not root.left and not root.right: return (0, 0) left_included, left_excluded = max_matching_helper(root.left) right_included, right_excluded = max_matching_helper(root.right) # Maximum matching gincluding current node curr_included = max(max(left_included, right_excluded) + 1, max(left_excluded, right_included) + 1) # Maximum matching excluding current node curr_excluded = left_included + right_included return (curr_included, curr_excluded) def max_matching(root): # Taking 1 as a root of the tree root_including, root_excluding = max_matching_helper(root) # Return maximum Matching return max(root_including, root_excluding) # Driver code root = Node(1) root.left = Node(2) root.right = Node(7) root.left.left = Node(3) root.left.right = Node(4) root.left.right.left = Node(5) root.left.right.right = Node(6) root.right.left = Node(8) root.right.right = Node(9) print(max_matching(root)) # This code is contributed by Rathijeet Bhave
3
Complejidad temporal : O(V + E), donde V es el número de aristas y E es el número de aristas.
Espacio Auxiliar : O(V)