Número de componentes conectados en una lista doblemente enlazada

Dada una lista doblemente enlazada ‘L’ y una array ‘refArr’ de referencias a los Nodes de la lista doblemente enlazada ‘L’. La array ‘refArr’ no contiene referencias duplicadas y las referencias no están ORDENADAS . 
m <= número total de Nodes en la lista doblemente enlazada donde m = tamaño de la array de referencia. 
La tarea es encontrar el número total de componentes conectados en la lista enlazada ‘L’. 

Un ‘ componente conectado ‘ en la lista enlazada ‘L’ se define como un grupo de Nodes en la lista con sus referencias almacenadas en la array ‘refArr’ y son adyacentes entre sí en la lista.

Ejemplos: 

Entrada: L = 5 <-> 2 <-> 10 <-> 1 <-> 3, refArr[] = {5, 10, 3, 1} 
Salida: 2 
Dos componentes conectados son 5 y 10 <-> 1 < -> 3. 
Dado que 2 no está incluido en la array de referencia, eso hace que 5 esté desconectado del resto de los elementos.

Entrada: L = 1 <-> 7 <-> 10 <-> 5 <-> 4 <-> 2, refArr[] = {5, 2, 7, 1} 
Salida: el número total de componentes conectados es 3 
 

Explicación:  

Tomemos una lista de doble enlace ‘L’ como { N1 N2 N3 N4 N5 N6 } 
y la array ‘refArr’ como [ref_to_nodeN1, ref_to_nodeN4, ref_to_nodeN6, ref_to_nodeN2].
Salida: 
este conjunto de array ‘refArr’ y lista vinculada ‘L’ contiene 3 componentes conectados , que son { [N1, N2], [N4], [N6] }. 
Es porque las referencias de los Nodes N1 y N2 están presentes en la array ‘refArr’ y son adyacentes entre sí en la lista ‘L’ mientras que N4 y N6 no son adyacentes a N1, N2 o entre sí. Por lo tanto, forman componentes separados.
Ahora, deje que la array ‘refArr’ se modifique como [ref_to_nodeN4, ref_to_nodeN6, ref_to_nodeN5].
Salida: 
este conjunto de array ‘refArr’ y lista vinculada ‘L’ contiene 1 componente conectado, que es { [N4, N5, N6] } . 
Es porque las referencias de los Nodes N4, N5 y N6 están presentes en la array ‘refArr’ y son adyacentes entre sí en la lista ‘L’. Entonces, juntos formamos 1 componente conectado.

Enfoque ingenuo: implica atravesar la array ‘refArr’ para cada Node de la lista vinculada ‘L’ y verificar si ese elemento está presente en la array o no. Además, mantenga una variable booleana que realice un seguimiento de si el Node anterior en la lista vinculada está en la array o no. Tome una variable ‘cc’ que se inicializa a 0 e indica el no. de componentes conectados en la lista enlazada.

 Ahora, consideremos los múltiples casos que ocurren mientras se atraviesa: 

• Caso 1: si el Node anterior está en la array y el Node actual que se está recorriendo también está en la array, la variable booleana permanecerá en 1, lo que significa que el Node actual está en la array, pero no incremente la variable ‘cc’ desde el Node actual forma parte del componente ya existente para el Node anterior.
• Caso 2: si el Node anterior no está en la array y el Node actual que se está recorriendo está en la array, actualice la variable booleana para marcar ‘1’, lo que significa que el Node actual está en la array y también incremente la variable ‘cc’ por 1 porque el Node actual forma un nuevo componente.
• Caso 3: si el Node anterior está en la array y el Node actual que se está recorriendo no está en la array, actualice la variable booleana para marcar 0, lo que significa que el Node actual no está en la array y no incremente la variable ‘cc’ ya que el Node actual no es parte de ningún componente.
• Caso 4: si el Node anterior no está en la array y el Node actual que se está recorriendo tampoco está en la array, la variable booleana permanecerá en 0, lo que significa que el Node actual no está en la array y no incrementa la variable ‘cc’ ya que el Node actual no es parte de ningún componente.

Ahora, después de realizar uno de los 4 casos, muévase al siguiente Node en la lista vinculada y haga lo mismo para ese Node también.

Complejidad de tiempo: O(n*m), donde n = tamaño de la lista enlazada ‘L’ Y, m = tamaño de la array de referencia ‘refArr’. 
Complejidad espacial: O(1) 

Mejor enfoque: este enfoque implica el uso de unordered_set . Tome una variable ‘componentes conectados’ que se inicializa en 0. componentes conectados indica el número de componentes conectados en la lista enlazada. 

Ahora, para cada elemento en la array de referencia ‘refArr’: 

• Agregue la referencia almacenada en la array a un ‘refSet’ unordered_set.
• Si tanto el hermano anterior como el siguiente están presentes, disminuya la variable ‘componentes conectados’ en 1, lo que significa que hemos cerrado una brecha entre dos componentes, por lo que debemos disminuir los componentes contados incorrectamente.
• Si solo uno de los hermanos anterior y siguiente está presente en el conjunto, entonces no se actualiza el no. de componentes
• Si ninguno de los hermanos anterior y siguiente está presente en el conjunto, entonces debemos incrementar los componentes contados incorrectamente porque ahora, el Node actual forma un nuevo componente.

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

// A C++ program to find number
// of Connected Components in a doubly linked list.
#include <bits/stdc++.h>
using namespace std;
 
// Node of the doubly linked list
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
 
// Function to find number of connected
// components using a doubly linked list
// and a reference array
int func_connComp(struct Node** head_ref,
                  vector<struct Node*> refArr, int n)
{
    // Base case when the doubly
    // linked list is empty
    if (head_ref == NULL) {
        return 0;
    }
 
    // Initialise connectedComponents to zero
    int connectedComponents = 0;
 
    // Initialise an unordered set
    unordered_set<struct Node*> refSet;
 
    // Push the first element of the
    // refArr in the refSet and
    // set the connectedComponents to 1
    refSet.insert(refArr[0]);
    connectedComponents++;
 
    // Loop over all the elements of the refArr
    for (int i = 1; i < n; i++) {
 
        // insert each reference node to the refSet
        refSet.insert(refArr[i]);
 
        // If the reference node is the head of the linked list
        if (refArr[i]->prev == NULL) {
 
            // when next sibling of the head node is
            // not in the refSet
            if (refSet.find(refArr[i]->next) == refSet.end()) {
                connectedComponents++;
            }
        }
 
        // If the reference node is the
        // last node of the linked list*/
        else if (refArr[i]->next == NULL) {
 
            // when previous sibling of the
            // node is not in the refSet
            if (refSet.find(refArr[i]->next) == refSet.end()) {
                connectedComponents++;
            }
        }
 
        // the case when both previous and
        // next siblings of the current node
        // are in the refSet
        else if (refSet.find(refArr[i]->prev) != refSet.end()
                 && refSet.find(refArr[i]->next) != refSet.end()) {
            connectedComponents--;
        }
 
        /*the case when previous and next
        // siblings of the current node
        // are not in the refSet*/
        else if (refSet.find(refArr[i]->prev) == refSet.end()
                 && refSet.find(refArr[i]->next) == refSet.end()) {
            connectedComponents++;
        }
    }
    return connectedComponents;
}
 
// Function to insert a node at the
// beginning of the Doubly Linked List
Node* push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = new Node;
 
    struct Node* current_node = new_node;
    /* put in the data */
    new_node->data = new_data;
 
    /* since we are adding at the beginning,
    prev is always NULL */
    new_node->prev = NULL;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* change prev of head node to new node */
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
 
    return current_node;
}
 
// Function to print nodes in a given
// doubly linked list
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
// Driver code
int main()
{
 
    // Start with the empty list
    struct Node* head = NULL;
 
    // Let us create a linked list to test
    // the functions so as to find number
    // of Connected Components Created a
    // doubly linked list: 1 <-> 7 <-> 10 <-> 5 <-> 4 <-> 2
    struct Node* ref_to_nodeN2 = push(&head, 2);
    struct Node* ref_to_nodeN4 = push(&head, 4);
    struct Node* ref_to_nodeN5 = push(&head, 5);
    struct Node* ref_to_nodeN10 = push(&head, 10);
    struct Node* ref_to_nodeN7 = push(&head, 7);
    struct Node* ref_to_nodeN1 = push(&head, 1);
 
    vector<struct Node*> refArr{ ref_to_nodeN5,
                                         ref_to_nodeN2, ref_to_nodeN7, ref_to_nodeN1 };
 
    // This function will return the number
    // of connected components of doubly linked list
    int connectedComponents = func_connComp(&head, refArr, 4);
 
    cout << "Total number of connected components are "
         << connectedComponents << endl;
 
    return 0;
}

// Java program to find number
// of Connected Components in a doubly linked list.
import java.util.HashSet;
 
public class GFG
{
   
  // Node of the doubly linked list
  static class Node {
    int data;
    Node next;
    Node prev;
  }
 
  // Function to find number of connected
  // components using a doubly linked list
  // and a reference array
  static int func_connComp(Node head_ref, Node[] refArr,
                           int n)
  {
    // Base case when the doubly
    // linked list is empty
    if (head_ref == null) {
      return 0;
    }
 
    // Initialise connectedComponents to zero
    int connectedComponents = 0;
 
    // Initialise an unordered set
    HashSet<Node> refSet = new HashSet<Node>();
 
    // Push the first element of the
    // refArr in the refSet and
    // set the connectedComponents to 1
    refSet.add(refArr[0]);
    connectedComponents++;
 
    // Loop over all the elements of the refArr
    for (int i = 1; i < n; i++) {
 
      // insert each reference node to the refSet
      refSet.add(refArr[i]);
 
      // If the reference node is the head of the
      // linked list
      if (refArr[i].prev == null) {
 
        // when next sibling of the head node is
        // not in the refSet
        if (refSet.contains(refArr[i].next)) {
          connectedComponents++;
        }
      }
 
      // If the reference node is the
      // last node of the linked list*/
      else if (refArr[i].next == null) {
 
        // when previous sibling of the
        // node is not in the refSet
        if (refSet.contains(refArr[i].next)) {
          connectedComponents++;
        }
      }
 
      // the case when both previous and
      // next siblings of the current node
      // are in the refSet
      else if (refSet.contains(refArr[i].prev)
               && refSet.contains(refArr[i].next)) {
        connectedComponents--;
      }
 
      /*the case when previous and next
            // siblings of the current node
            // are not in the refSet*/
      else if (!refSet.contains(refArr[i].prev)
               && !refSet.contains(refArr[i].next)) {
        connectedComponents++;
      }
    }
    return connectedComponents;
  }
 
  // Function to insert a node at the
  // beginning of the Doubly Linked List
  static Node push(int new_data)
  {
    /* allocate node */
    Node new_node = new Node();
 
    Node current_node = new_node;
    /* put in the data */
    new_node.data = new_data;
 
    /* since we are adding at the beginning,
        prev is always null */
    new_node.prev = null;
 
    /* link the old list off the new node */
    new_node.next = head;
 
    /* change prev of head node to new node */
    if ((head) != null)
      head.prev = new_node;
 
    /* move the head to point to the new node */
    head = new_node;
 
    return current_node;
  }
 
  // Function to print nodes in a given
  // doubly linked list
  static void printList(Node node)
  {
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }
 
  // Start with the empty list
  static Node head = null;
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Let us create a linked list to test
    // the functions so as to find number
    // of Connected Components Created a
    // doubly linked list: 1 <. 7 <. 10 <. 5 <. 4 <. 2
    Node ref_to_nodeN2 = push(2);
    Node ref_to_nodeN4 = push(4);
    Node ref_to_nodeN5 = push(5);
    Node ref_to_nodeN10 = push(10);
    Node ref_to_nodeN7 = push(7);
    Node ref_to_nodeN1 = push(1);
 
    Node[] refArr = { ref_to_nodeN5, ref_to_nodeN2,
                     ref_to_nodeN7, ref_to_nodeN1 };
 
    // This function will return the number
    // of connected components of doubly linked list
    int connectedComponents
      = func_connComp(head, refArr, 4);
 
    System.out.println(
      "Total number of connected components are "
      + connectedComponents);
  }
}
 
// This code is contributed by Lovely Jain

# A Python3 program to find number
# of Connected Components in a doubly linked list.
  
# Node of the doubly linked list
class Node:  
    def __init__(self):      
        self.data = 0
        self.next = None
        self.prev = None
         
# Function to find number of connected
# components using a doubly linked list
# and a reference array
def func_connComp(head_ref, refArr, n):
     
    # Base case when the doubly
    # linked list is empty
    if (head_ref == None):
        return 0;
  
    # Initialise connectedComponents to zero
    connectedComponents = 0;
  
    # Initialise an unordered set
    refSet = set()
  
    # Push the first element of the
    # refArr in the refSet and
    # set the connectedComponents to 1
    refSet.add(refArr[0]);
    connectedComponents += 1
  
    # Loop over all the elements of the refArr
    for i in range(1, n):
  
        # add each reference node to the refSet
        refSet.add(refArr[i]);
  
        # If the reference node is the head of the linked list
        if (refArr[i].prev == None):
  
            # when next sibling of the head node is
            # not in the refSet
            if (refArr[i].next not in refSet):
                connectedComponents += 1
  
        # If the reference node is the
        # last node of the linked list'''
        elif (refArr[i].next == None):
  
            # when previous sibling of the
            # node is not in the refSet
            if (refArr[i].next not in refSet):
                connectedComponents += 1
              
        # the case when both previous and
        # next siblings of the current node
        # are in the refSet
        elif (refArr[i].prev in refSet
              and refArr[i].next in refSet):
            connectedComponents -= 1
             
        # the case when previous and next
        # siblings of the current node
        # are not in the refSet'''
        elif (refArr[i].prev not in refSet
              and refArr[i].next not in refSet):
            connectedComponents += 1
           
    return connectedComponents;
  
# Function to add a node at the
# beginning of the Doubly Linked List
def push(head_ref, new_data):
 
    ''' allocate node '''
    new_node = Node()
    current_node = new_node;
     
    ''' put in the data '''
    new_node.data = new_data;
  
    ''' since we are adding at the beginning,
    prev is always None '''
    new_node.prev = None;
  
    ''' link the old list off the new node '''
    new_node.next = (head_ref);
  
    ''' change prev of head node to new node '''
    if ((head_ref) != None):
        (head_ref).prev = new_node;
  
    ''' move the head to point to the new node '''
    (head_ref) = new_node;
    return current_node, head_ref;
  
# Function to print nodes in a given
# doubly linked list
def printList(node):
    while (node != None):
        print(node.data, end = ' ');
        node = node.next;
         
# Driver code
if __name__=='__main__':
  
    # Start with the empty list
    head = None;
  
    # Let us create a linked list to test
    # the functions so as to find number
    # of Connected Components Created a
    # doubly linked list: 1 <. 7 <. 10 <. 5 <. 4 <. 2
    ref_to_nodeN2, head = push(head, 2);
    ref_to_nodeN4, head = push(head, 4)
    ref_to_nodeN5, head = push(head, 5)
    ref_to_nodeN10, head = push(head, 10)
    ref_to_nodeN7, head = push(head, 7)
    ref_to_nodeN1, head = push(head, 1)  
    refArr = [ref_to_nodeN5, ref_to_nodeN2, ref_to_nodeN7, ref_to_nodeN1]
  
    # This function will return the number
    # of connected components of doubly linked list
    connectedComponents = func_connComp(head, refArr, 4);
    print("Total number of connected components are ", connectedComponents)
 
  # This code is contributed by rutvik_56

Total number of connected components are 3

Complejidad de tiempo: O(m) 
Complejidad de espacio: O(m) Donde, m = tamaño de la array de referencia ‘refArr’