Compruebe si un árbol se puede dividir en K componentes conectados iguales

Posted on by Rudeus Greyrat

Dada la representación de la Lista de Adyacencia de un árbol y un número entero K ., la tarea es encontrar si el árbol dado se puede dividir en K Componentes Conectados iguales o no.
Nota : se dice que dos componentes conectados son iguales si contienen el mismo número de Nodes.

Ejemplos: 

Entrada: N = 15, K = 5 
A continuación se muestra el árbol dado con Número de Nodes = 15 
 

Salida: SÍ 
Explicación: 
A continuación se muestra el número de 5 componentes conectados que se pueden hacer: 
 

Enfoque: 
La idea es utilizar el recorrido de búsqueda en profundidad primero (DFS) en el árbol dado de N Nodes para encontrar si el árbol dado se puede dividir en K componentes conectados iguales o no. Los siguientes son los pasos: 

  1. Inicie DFS Traversal con la raíz del árbol.
  2. Para cada vértice no visitado durante el recorrido de DFS , llame recursivamente a DFS para ese vértice manteniendo el recuento de Nodes recorridos durante cada llamada recursiva de DFS.
  3. Si el recuento de Nodes es igual a (N/K) , entonces obtuvimos uno del conjunto de componentes conectados .
  4. Si el número total del conjunto de Componentes Conectados de ( N/K ) Nodes es igual a K. Luego, el gráfico dado se puede dividir en K es igual a Componentes Conectados .

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to detect whether
// the given Tree can be split
// into K equals components
#include <bits/stdc++.h>
using namespace std;
 
// For checking if the graph
// can be split into K equal
// Connected Components
int flag = 0;
 
// DFS Traversal
int DFS(vector<int> adj[], int k,
        int i, int x)
{
 
    // Initialise ans to 1
    int ans = 1;
 
    // Traverse the adjacency
    // for vertex i
    for (auto& it : adj[i]) {
        if (it != k) {
            ans += DFS(adj, i, it, x);
        }
    }
 
    // If number of nodes is
    // greater than x, then
    // the tree cannot be split
    if (ans > x) {
        flag = 1;
        return 0;
    }
 
    // Check for requirement
    // of nodes
    else if (ans == x) {
        ans = 0;
    }
    return ans;
}
 
// A utility function to add
// an edge in an undirected
// Tree
void addEdge(vector<int> adj[],
             int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
 
// Driver's Code
int main()
{
    int N = 15, K = 5;
 
    // Adjacency List
    vector<int> adj[N + 1];
 
    // Adding edges to List
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 5, 7);
    addEdge(adj, 4, 8);
    addEdge(adj, 4, 9);
    addEdge(adj, 8, 11);
    addEdge(adj, 10, 11);
    addEdge(adj, 11, 14);
    addEdge(adj, 9, 12);
    addEdge(adj, 12, 15);
    addEdge(adj, 12, 13);
 
    // Check if tree can be split
    // into K Connected Components
    // of equal number of nodes
    if (N % K == 0) {
        // DFS call to Check
        // if tree can be split
        DFS(adj, -1, 1, N / K);
    }
 
    // If flag is 0, then the
    // given can be split to
    // Connected Components
    cout << (flag ? "NO" : "YES");
 
    return 0;
}

Java

// Java program to detect whether
// the given Tree can be split
// into K equals components
import java.util.*;
 
class GFG
{
  
// For checking if the graph
// can be split into K equal
// Connected Components
static int flag = 0;
  
// DFS Traversal
static int DFS(Vector<Integer> adj[], int k,
        int i, int x)
{
  
    // Initialise ans to 1
    int ans = 1;
  
    // Traverse the adjacency
    // for vertex i
    for (int it : adj[i]) {
        if (it != k) {
            ans += DFS(adj, i, it, x);
        }
    }
  
    // If number of nodes is
    // greater than x, then
    // the tree cannot be split
    if (ans > x) {
        flag = 1;
        return 0;
    }
  
    // Check for requirement
    // of nodes
    else if (ans == x) {
        ans = 0;
    }
    return ans;
}
  
// A utility function to add
// an edge in an undirected
// Tree
static void addEdge(Vector<Integer> adj[],
             int u, int v)
{
    adj[u].add(v);
    adj[v].add(u);
}
  
// Driver's Code
public static void main(String[] args)
{
    int N = 15, K = 5;
  
    // Adjacency List
    Vector<Integer> []adj = new Vector[N + 1];
    for(int i= 0; i < N + 1; i++)
        adj[i] = new Vector<Integer>();
     
    // Adding edges to List
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 5, 7);
    addEdge(adj, 4, 8);
    addEdge(adj, 4, 9);
    addEdge(adj, 8, 11);
    addEdge(adj, 10, 11);
    addEdge(adj, 11, 14);
    addEdge(adj, 9, 12);
    addEdge(adj, 12, 15);
    addEdge(adj, 12, 13);
  
    // Check if tree can be split
    // into K Connected Components
    // of equal number of nodes
    if (N % K == 0) {
        // DFS call to Check
        // if tree can be split
        DFS(adj, -1, 1, N / K);
    }
  
    // If flag is 0, then the
    // given can be split to
    // Connected Components
    System.out.print(flag==1 ? "NO" : "YES");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to detect whether
# the given Tree can be split
# into K equals components
 
# For checking if the graph
# can be split into K equal
# Connected Components
flag = 0
 
# DFS Traversal
def DFS(adj, k, i, x):
     
    # Initialise ans to 1
    ans = 1
    
    # Traverse the adjacency
    # for vertex i
    for it in adj[i]:
        if it is not k:
            ans += DFS(adj, i, it, x)
             
    # If number of nodes is
    # greater than x, then
    # the tree cannot be split
    if (ans > x):
        flag = 1
        return 0
    
    # Check for requirement
    # of nodes
    elif (ans == x):
        ans = 0
     
    return ans
 
# A utility function to add
# an edge in an undirected
# Tree
def addEdge(adj, u, v):
     
    adj[u].append(v)
    adj[v].append(u)
 
# Driver code
if __name__=="__main__":
     
    (N, K) = (15, 5)
     
    # Adjacency List
    adj = [[] for i in range(N + 1)]
     
    # Adding edges to List
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 5, 7);
    addEdge(adj, 4, 8);
    addEdge(adj, 4, 9);
    addEdge(adj, 8, 11);
    addEdge(adj, 10, 11);
    addEdge(adj, 11, 14);
    addEdge(adj, 9, 12);
    addEdge(adj, 12, 15);
    addEdge(adj, 12, 13);
     
    # Check if tree can be split
    # into K Connected Components
    # of equal number of nodes
    if (N % K == 0):
         
        # DFS call to Check
        # if tree can be split
        DFS(adj, -1, 1, N // K)
    
    # If flag is 0, then the
    # given can be split to
    # Connected Components
    if flag == 1:
        print("NO")
    else:
        print("YES")
 
# This code is contributed by rutvik_56

C#

// C# program to detect whether
// the given Tree can be split
// into K equals components
using System;
using System.Collections.Generic;
 
class GFG
{
   
// For checking if the graph
// can be split into K equal
// Connected Components
static int flag = 0;
   
// DFS Traversal
static int DFS(List<int> []adj, int k,
        int i, int x)
{
   
    // Initialise ans to 1
    int ans = 1;
   
    // Traverse the adjacency
    // for vertex i
    foreach (int it in adj[i]) {
        if (it != k) {
            ans += DFS(adj, i, it, x);
        }
    }
   
    // If number of nodes is
    // greater than x, then
    // the tree cannot be split
    if (ans > x) {
        flag = 1;
        return 0;
    }
   
    // Check for requirement
    // of nodes
    else if (ans == x) {
        ans = 0;
    }
    return ans;
}
   
// A utility function to add
// an edge in an undirected
// Tree
static void addEdge(List<int> []adj,
             int u, int v)
{
    adj[u].Add(v);
    adj[v].Add(u);
}
   
// Driver's Code
public static void Main(String[] args)
{
    int N = 15, K = 5;
   
    // Adjacency List
    List<int> []adj = new List<int>[N + 1];
    for(int i= 0; i < N + 1; i++)
        adj[i] = new List<int>();
      
    // Adding edges to List
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 4, 5);
    addEdge(adj, 5, 6);
    addEdge(adj, 5, 7);
    addEdge(adj, 4, 8);
    addEdge(adj, 4, 9);
    addEdge(adj, 8, 11);
    addEdge(adj, 10, 11);
    addEdge(adj, 11, 14);
    addEdge(adj, 9, 12);
    addEdge(adj, 12, 15);
    addEdge(adj, 12, 13);
   
    // Check if tree can be split
    // into K Connected Components
    // of equal number of nodes
    if (N % K == 0) {
        // DFS call to Check
        // if tree can be split
        DFS(adj, -1, 1, N / K);
    }
   
    // If flag is 0, then the
    // given can be split to
    // Connected Components
    Console.Write(flag==1 ? "NO" : "YES");
}
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
  
 
// Javascript program to detect whether
// the given Tree can be split
// into K equals components
 
// For checking if the graph
// can be split into K equal
// Connected Components
var flag = 0;
 
// DFS Traversal
function DFS(adj, k, i, x)
{
 
    // Initialise ans to 1
    var ans = 1;
 
    // Traverse the adjacency
    // for vertex i
    adj[i].forEach(element => {
        if (element != k) {
            ans += DFS(adj, i, element, x);
        }
    });
 
    // If number of nodes is
    // greater than x, then
    // the tree cannot be split
    if (ans > x) {
        flag = 1;
        return 0;
    }
 
    // Check for requirement
    // of nodes
    else if (ans == x) {
        ans = 0;
    }
    return ans;
}
 
// A utility function to add
// an edge in an undirected
// Tree
function addEdge(adj, u, v)
{
    adj[u].push(v);
    adj[v].push(u);
}
 
// Driver's Code
var N = 15, K = 5;
// Adjacency List
var adj = Array.from(Array(N+1), ()=> Array());
// Adding edges to List
addEdge(adj, 1, 2);
addEdge(adj, 2, 3);
addEdge(adj, 2, 4);
addEdge(adj, 4, 5);
addEdge(adj, 5, 6);
addEdge(adj, 5, 7);
addEdge(adj, 4, 8);
addEdge(adj, 4, 9);
addEdge(adj, 8, 11);
addEdge(adj, 10, 11);
addEdge(adj, 11, 14);
addEdge(adj, 9, 12);
addEdge(adj, 12, 15);
addEdge(adj, 12, 13);
// Check if tree can be split
// into K Connected Components
// of equal number of nodes
if (N % K == 0) {
    // DFS call to Check
    // if tree can be split
    DFS(adj, -1, 1, N / K);
}
// If flag is 0, then the
// given can be split to
// Connected Components
document.write(flag ? "NO" : "YES");
 
 
</script>
Producción: 

YES

 

Complejidad temporal: O(V + E), donde V es el número de vértices y E es el número de aristas
 

Publicación traducida automáticamente

Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *