Cuente los subgráficos aislados de un solo Node en un gráfico desconectado

Se da un Gráfico desconectado con N vértices y K aristas. La tarea es encontrar el recuento de subgráficos singleton. Un gráfico singleton es uno con un solo vértice.

Ejemplos: 

Input : 
Vertices : 6
Edges :    1 2
           1 3
           5 6
Output : 1
Explanation :  The Graph has 3 components : {1-2-3}, {5-6}, {4}
Out of these, the only component forming singleton graph is {4}.

La idea es simple para el gráfico dado como representación de lista de adyacencia. Recorremos la lista y encontramos los índices (que representan un Node) sin elementos en la lista, es decir, sin componentes conectados.

A continuación se muestra la representación: 

// CPP code to count the singleton sub-graphs
// in a disconnected graph
#include <bits/stdc++.h>
using namespace std;
 
// Function to compute the count
int compute(vector<int> graph[], int N)
{
    // Storing intermediate result
    int count = 0;
 
    // Traversing the Nodes
    for (int i = 1; i <= N; i++)
 
        // Singleton component
        if (graph[i].size() == 0)
            count++;   
 
    // Returning the result
    return count;
}
 
// Driver
int main()
{
    // Number of nodes
    int N = 6;
 
    // Adjacency list for edges 1..6
    vector<int> graph[7];
 
    // Representing edges
    graph[1].push_back(2);
    graph[2].push_back(1);
 
    graph[2].push_back(3);
    graph[3].push_back(2);
 
    graph[5].push_back(6);
    graph[6].push_back(5);
 
    cout << compute(graph, N);
}

// Java code to count the singleton sub-graphs
// in a disconnected graph
import java.util.*;
 
class GFG
{
 
// Function to compute the count
static int compute(int []graph, int N)
{
    // Storing intermediate result
    int count = 0;
     
    // Traversing the Nodes
    for (int i = 1; i < 7; i++)
    {
        // Singleton component
        if (graph[i] == 0)
            count++;    
    }
         
    // Returning the result
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    // Number of nodes
    int N = 6;
 
    // Adjacency list for edges 1..6
    int []graph = new int[7];
    // Representing edges
    graph[1] = 2;
    graph[2] = 1;
    graph[2] = 3;
    graph[3] = 2;
    graph[5] = 6;
    graph[6] = 5;
 
    System.out.println(compute(graph, N));
}
}
 
// This code is contributed by PrinciRaj1992

# Python code to count the singleton sub-graphs
# in a disconnected graph
  
# Function to compute the count
def compute(graph, N):
    # Storing intermediate result
    count = 0
   
    # Traversing the Nodes
    for i in range(1, N+1):
   
        # Singleton component
        if (len(graph[i]) == 0):
            count += 1   
   
    # Returning the result
    return count
   
# Driver
if __name__ == '__main__':
 
    # Number of nodes
    N = 6
   
    # Adjacency list for edges 1..6
    graph = [[] for i in range(7)]
   
    # Representing edges
    graph[1].append(2)
    graph[2].append(1)
   
    graph[2].append(3)
    graph[3].append(2)
   
    graph[5].append(6)
    graph[6].append(5)
   
    print(compute(graph, N))

// C# code to count the singleton sub-graphs
// in a disconnected graph
using System;
 
class GFG
{
 
// Function to compute the count
static int compute(int []graph, int N)
{
    // Storing intermediate result
    int count = 0;
     
    // Traversing the Nodes
    for (int i = 1; i < 7; i++)
    {
        // Singleton component
        if (graph[i] == 0)
            count++;    
    }
         
    // Returning the result
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    // Number of nodes
    int N = 6;
 
    // Adjacency list for edges 1..6
    int []graph = new int[7];
     
    // Representing edges
    graph[1] = 2;
    graph[2] = 1;
    graph[2] = 3;
    graph[3] = 2;
    graph[5] = 6;
    graph[6] = 5;
 
    Console.WriteLine(compute(graph, N));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript code to count the singleton sub-graphs
// in a disconnected graph
 
// Function to compute the count
function compute(graph,N)
{
    // Storing intermediate result
    let count = 0;
       
    // Traversing the Nodes
    for (let i = 1; i < 7; i++)
    {
        // Singleton component
        if (graph[i].length == 0)
            count++;    
    }
           
    // Returning the result
    return count;
}
 
// Driver Code
// Number of nodes
let N = 6;
 
// Adjacency list for edges 1..6
let graph = new Array(7);
for(let i=0;i<7;i++)
{
    graph[i]=[];
}
// Representing edges
graph[1].push(2)
graph[2].push(1)
 
graph[2].push(3)
graph[3].push(2)
 
graph[5].push(6)
graph[6].push(5)
document.write(compute(graph, N));
 
// This code is contributed by rag2127
 
</script>

1

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.