Conteo de longitudes únicas de componentes conectados para un gráfico no dirigido usando STL

Dado un gráfico no dirigido, la tarea es encontrar el tamaño de cada componente conectado e imprimir el número de tamaños únicos de los componentes conectados.
 

Como se muestra arriba, el conteo (tamaño del componente conectado) asociado con los componentes conectados es 2, 3 y 2. Ahora, el conteo único de los componentes es 2 y 3. Por lo tanto, el resultado esperado es Contar = 2
Ejemplos: 

Input: N = 7

Output: 1 2 Count = 2
        3 4 5 Count = 3
        6 7 Count = 2
        Unique Counts of connected components: 2

Input: N = 10

Output: 1 Count = 1
        2 3 4 5 Count = 4
        6 7 8 Count = 3
        9 10 Count = 2
        Unique Counts of connected components: 4

Requisitos previos: enfoque de búsqueda en profundidad primero : la idea básica es utilizar el método transversal de búsqueda en profundidad primero para realizar un seguimiento de los componentes conectados en el gráfico no dirigido. Un conjunto de contenedores STL se utiliza para almacenar los recuentos únicos de todos estos componentes, ya que se sabe que un conjunto tiene la propiedad de almacenar elementos únicos de manera ordenada. Finalmente, extraer el tamaño del Conjunto nos da el resultado necesario. La implementación paso a paso es la siguiente:  
 

1. Inicialice un contenedor hash (Set) para almacenar los recuentos únicos de los componentes conectados.
2. Llame de forma recursiva al recorrido de primera búsqueda en profundidad.
3. Por cada vértice visitado, almacene el conteo en el contenedor establecido.
4. El tamaño final del Conjunto es el resultado requerido.

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

// C++ program to find unique count of
// connected components
#include <bits/stdc++.h>
using namespace std;
 
// Function to add edge in the graph
void add_edge(int u, int v, vector<int> graph[])
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}
 
// Function to traverse the undirected graph
// using DFS algorithm and keep a track of
// individual lengths of connected chains
void depthFirst(int v, vector<int> graph[],
                vector<bool>& visited, int& ans)
{
    // Marking the visited vertex as true
    visited[v] = true;
    cout << v << " ";
 
    // Incrementing the count of
    // connected chain length
    ans++;
 
    for (auto i : graph[v]) {
        if (visited[i] == false) {
            // Recursive call to the DFS algorithm
            depthFirst(i, graph, visited, ans);
        }
    }
}
 
// Function to initialize the graph
// and display the result
void UniqueConnectedComponent(int n,
                              vector<int> graph[])
{
 
    // Initializing boolean visited array
    // to mark visited vertices
    vector<bool> visited(n + 1, false);
 
    // Initializing a Set container
    unordered_set<int> result;
 
    // Following loop invokes DFS algorithm
    for (int i = 1; i <= n; i++) {
        if (visited[i] == false) {
            // ans variable stores the
            // individual counts
            int ans = 0;
 
            // DFS algorithm
            depthFirst(i, graph, visited, ans);
 
            // Inserting the counts of connected
            // components in set
            result.insert(ans);
            cout << "Count = " << ans << "\n";
        }
    }
 
    cout << "Unique Counts of "
         << "connected components: ";
 
    // The size of the Set container
    // gives the desired result
    cout << result.size() << "\n";
}
 
// Driver code
int main()
{
    // Number of nodes
    int n = 7;
 
    // Create graph
    vector<int> graph[n + 1];
 
    // Constructing the undirected graph
    add_edge(1, 2, graph);
    add_edge(3, 4, graph);
    add_edge(3, 5, graph);
    add_edge(6, 7, graph);
 
    // Function call
    UniqueConnectedComponent(n, graph);
 
    return 0;
}

// Java program to find
// unique count of
// connected components
import java.util.*;
class GFG{
 
// Function to add edge in the graph
static void add_edge(int u, int v,
                    Vector<Integer> graph[])
{
graph[u].add(v);
graph[v].add(u);
}
 
// Function to traverse the undirected graph
// using DFS algorithm and keep a track of
// individual lengths of connected chains
static int depthFirst(int v,
                    Vector<Integer> graph[],
                    Vector<Boolean> visited,
                    int ans)
{
// Marking the visited vertex as true
visited.set(v, true);
System.out.print(v + " ");
 
// Incrementing the count of
// connected chain length
ans++;
 
for (int i : graph[v])
{
    if (visited.get(i) == false)
    {
    // Recursive call to the DFS algorithm
    ans = depthFirst(i, graph, visited, ans);
    }
}
return ans;
}
 
// Function to initialize the graph
// and display the result
static void UniqueConnectedComponent(int n,
                                    Vector<Integer> graph[])
{
// Initializing boolean visited array
// to mark visited vertices
Vector<Boolean> visited = new Vector<>();
for(int i = 0; i < n + 1; i++)
    visited.add(false);
 
// Initializing a Set container
HashSet<Integer> result = new HashSet<>();
 
// Following loop invokes DFS algorithm
for (int i = 1; i <= n; i++)
{
    if (visited.get(i) == false)
    {
    // ans variable stores the
    // individual counts
    int ans = 0;
 
    // DFS algorithm
    ans = depthFirst(i, graph, visited, ans);
 
    // Inserting the counts of connected
    // components in set
    result.add(ans);
    System.out.print("Count = " +
                        ans + "\n");
    }
}
System.out.print("Unique Counts of " +
                "connected components: ");
 
// The size of the Set container
// gives the desired result
System.out.print(result.size() + "\n");
}
 
// Driver code
public static void main(String[] args)
{
// Number of nodes
int n = 7;
 
// Create graph
@SuppressWarnings("unchecked")
Vector<Integer>[] graph = new Vector[n+1];
for (int i = 0; i < graph.length; i++)
    graph[i] = new Vector<Integer>();
 
// Constructing the undirected graph
add_edge(1, 2, graph);
add_edge(3, 4, graph);
add_edge(3, 5, graph);
add_edge(6, 7, graph);
 
// Function call
UniqueConnectedComponent(n, graph);
}
}

# Python3 program to find unique count of
# connected components
graph = [[] for i in range(100 + 1)]
visited = [False] * (100 + 1)
ans = 0
 
# Function to add edge in the graph
def add_edge(u, v):
     
    graph[u].append(v)
    graph[v].append(u)
 
# Function to traverse the undirected graph
# using DFS algorithm and keep a track of
# individual lengths of connected chains
def depthFirst(v):
     
    global ans
     
    # Marking the visited vertex as true
    visited[v] = True
    print(v, end = " ")
    #print(ans,end="-")
 
    # Incrementing the count of
    # connected chain length
    ans += 1
 
    for i in graph[v]:
        if (visited[i] == False):
             
            # Recursive call to the
            # DFS algorithm
            depthFirst(i)
 
# Function to initialize the graph
# and display the result
def UniqueConnectedComponent(n):
     
    global ans
 
    # Initializing boolean visited array
    # to mark visited vertices
 
    # Initializing a Set container
    result = {}
 
    # Following loop invokes DFS algorithm
    for i in range(1, n + 1):
        if (visited[i] == False):
             
            # ans variable stores the
            # individual counts
            # ans = 0
 
            # DFS algorithm
            depthFirst(i)
 
            # Inserting the counts of connected
            # components in set
            result[ans] = 1
            print("Count = ", ans)
            ans = 0
 
    print("Unique Counts of connected "
          "components: ", end = "")
 
    # The size of the Set container
    # gives the desired result
    print(len(result))
 
# Driver code
if __name__ == '__main__':
     
    # Number of nodes
    n = 7
 
    # Create graph
 
    # Constructing the undirected graph
    add_edge(1, 2)
    add_edge(3, 4)
    add_edge(3, 5)
    add_edge(6, 7)
 
    # Function call
    UniqueConnectedComponent(n)
 
# This code is contributed by mohit kumar 29

// C# program to find
// unique count of
// connected components
using System;
using System.Collections.Generic;
class GFG{
 
// Function to add edge in the graph
static void add_edge(int u, int v,
                     List<int> []graph)
{
  graph[u].Add(v);
  graph[v].Add(u);
}
 
// Function to traverse the undirected graph
// using DFS algorithm and keep a track of
// individual lengths of connected chains
static int depthFirst(int v,
                      List<int> []graph,
                      List<Boolean> visited,
                      int ans)
{
  // Marking the visited
  // vertex as true
  visited.Insert(v, true);
  Console.Write(v + " ");
 
  // Incrementing the count of
  // connected chain length
  ans++;
 
  foreach (int i in graph[v])
  {
    if (visited[i] == false)
    {
      // Recursive call to
      // the DFS algorithm
      ans = depthFirst(i, graph,
                       visited, ans);
    }
  }
  return ans;
}
 
// Function to initialize the graph
// and display the result
static void UniqueConnectedComponent(int n,
                                     List<int> []graph)
{
  // Initializing bool visited array
  // to mark visited vertices
  List<Boolean> visited = new List<Boolean>();
  for(int i = 0; i < n + 1; i++)
    visited.Add(false);
   
  // Initializing a Set container
  HashSet<int> result = new HashSet<int>();
 
  // Following loop invokes DFS algorithm
  for (int i = 1; i <= n; i++)
  {
    if (visited[i] == false)
    {
      // ans variable stores the
      // individual counts
      int ans = 0;
 
      // DFS algorithm
      ans = depthFirst(i, graph, visited, ans);
 
      // Inserting the counts of connected
      // components in set
      result.Add(ans);
      Console.Write("Count = " + 
                     ans + "\n");
    }
  }
  Console.Write("Unique Counts of " +
                "connected components: ");
 
  // The size of the Set container
  // gives the desired result
  Console.Write(result.Count + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
  // Number of nodes
  int n = 7;
 
  // Create graph
  List<int> []graph = new List<int>[n + 1];
  for (int i = 0; i < graph.Length; i++)
    graph[i] = new List<int>();
 
  // Constructing the undirected graph
  add_edge(1, 2, graph);
  add_edge(3, 4, graph);
  add_edge(3, 5, graph);
  add_edge(6, 7, graph);
 
  // Function call
  UniqueConnectedComponent(n, graph);
}
}
 
// This code is contributed by shikhasingrajput

<script>
// Javascript program to find
// unique count of
// connected components
 
// Function to add edge in the graph
function add_edge(u,v,graph)
{
    graph[u].push(v);
  graph[v].push(u);
}
 
// Function to traverse the undirected graph
// using DFS algorithm and keep a track of
// individual lengths of connected chains
function depthFirst(v, graph,visited,ans)
{
    // Marking the visited vertex as true
  visited[v] = true;
  document.write(v + " ");
  
  // Incrementing the count of
  // connected chain length
  ans++;
  
  for (let i=0;i< graph[v].length;i++)
  {
    if (visited[graph[v][i]] == false)
    {
      // Recursive call to the DFS algorithm
      ans = depthFirst(graph[v][i], graph, visited, ans);
    }
  }
  return ans;
}
 
// Function to initialize the graph
// and display the result
function UniqueConnectedComponent(n,graph)
{
    // Initializing boolean visited array
  // to mark visited vertices
  let visited = [];
  for(let i = 0; i < n + 1; i++)
    visited.push(false);
    
  // Initializing a Set container
  let result = new Set();
  
  // Following loop invokes DFS algorithm
  for (let i = 1; i <= n; i++)
  {
    if (visited[i] == false)
    {
      // ans variable stores the
      // individual counts
      let ans = 0;
  
      // DFS algorithm
      ans = depthFirst(i, graph, visited, ans);
  
      // Inserting the counts of connected
      // components in set
      result.add(ans);
      document.write("Count = " +
                        ans + "<br>");
    }
  }
  document.write("Unique Counts of " +
                   "connected components: ");
  
  // The size of the Set container
  // gives the desired result
  document.write(result.size + "<br>");
}
 
// Driver code
 
// Number of nodes
let n = 7;
 
// Create graph
let graph = new Array(n + 1);
for (let i = 0; i < graph.length; i++)
    graph[i] = [];
 
// Constructing the undirected graph
add_edge(1, 2, graph);
add_edge(3, 4, graph);
add_edge(3, 5, graph);
add_edge(6, 7, graph);
 
// Function call
UniqueConnectedComponent(n, graph);
 
 
// This code is contributed by patel2127
</script>

1 2 Count = 2
3 4 5 Count = 3
6 7 Count = 2
Unique Counts of connected components: 2

Complejidad de tiempo: 
como se desprende de la implementación anterior, el gráfico se recorre utilizando el algoritmo de búsqueda en profundidad primero. Los recuentos individuales se almacenan utilizando el contenedor Set en el que la operación de inserción tarda O (1) tiempo. La complejidad general se basa únicamente en el tiempo que tarda el algoritmo DFS en ejecutarse de forma recursiva. Por lo tanto, la complejidad temporal del programa es O(E + V) donde E es el número de aristas y V es el número de vértices del gráfico. 
Espacio Auxiliar: O(N)