Número de Nodes receptores en un gráfico

Dado un gráfico acíclico dirigido de n Nodes (numerados del 1 al n) y m aristas. La tarea es encontrar el número de Nodes sumideros. Un Node sumidero es un Node del que no emerge ningún borde.

Ejemplos: 

Input : n = 4, m = 2
        Edges[] = {{2, 3}, {4, 3}} 
Output : 2

Only node 1 and node 3 are sink nodes.

Input : n = 4, m = 2
        Edges[] = {{3, 2}, {3, 4}} 
Output : 3

La idea es iterar a través de todos los bordes. Y para cada borde, marque el Node de origen del que salió el borde. Ahora, para cada Node, compruebe si está marcado o no. Y cuenta los Nodes sin marcar. 

Algoritmo: 

 
1. Make any array A[] of size equal to the
    number of nodes and initialize to 1.
2. Traverse all the edges one by one, say, 
   u -> v.
     (i) Mark A[u] as 1.
3. Now traverse whole array A[] and count 
   number of unmarked nodes.

A continuación se muestra la implementación de este enfoque:  

// C++ program to count number if sink nodes
#include<bits/stdc++.h>
using namespace std;
  
// Return the number of Sink NOdes.
int countSink(int n, int m, int edgeFrom[],
                        int edgeTo[])
{
    // Array for marking the non-sink node.
    int mark[n];
    memset(mark, 0, sizeof mark);
  
    // Marking the non-sink node.
    for (int i = 0; i < m; i++)
        mark[edgeFrom[i]] = 1;
  
    // Counting the sink nodes.
    int count = 0;
    for (int i = 1; i <= n ; i++)
        if (!mark[i])
            count++;
  
    return count;
}
  
// Driven Program
int main()
{
    int n = 4, m = 2;
    int edgeFrom[] = { 2, 4 };
    int edgeTo[] = { 3, 3 };
  
    cout << countSink(n, m, edgeFrom, edgeTo) << endl;
  
    return 0;
}

// Java program to count number if sink nodes
import java.util.*;
  
class GFG
{
  
// Return the number of Sink NOdes.
static int countSink(int n, int m, 
                     int edgeFrom[], int edgeTo[])
{
    // Array for marking the non-sink node.
    int []mark = new int[n + 1];
  
    // Marking the non-sink node.
    for (int i = 0; i < m; i++)
        mark[edgeFrom[i]] = 1;
  
    // Counting the sink nodes.
    int count = 0;
    for (int i = 1; i <= n ; i++)
        if (mark[i] == 0)
            count++;
  
    return count;
}
  
// Driver Code
public static void main(String[] args)
{
    int n = 4, m = 2;
    int edgeFrom[] = { 2, 4 };
    int edgeTo[] = { 3, 3 };
  
    System.out.println(countSink(n, m, 
                       edgeFrom, edgeTo));
}
}
  
// This code is contributed by 29AjayKumar

# Python3 program to count number if sink nodes
  
# Return the number of Sink NOdes. 
def countSink(n, m, edgeFrom, edgeTo):
      
    # Array for marking the non-sink node. 
    mark = [0] * (n + 1)
  
    # Marking the non-sink node.
    for i in range(m):
        mark[edgeFrom[i]] = 1
  
    # Counting the sink nodes. 
    count = 0
    for i in range(1, n + 1):
        if (not mark[i]): 
            count += 1
  
    return count
  
# Driver Code
if __name__ == '__main__': 
      
    n = 4
    m = 2
    edgeFrom = [2, 4] 
    edgeTo = [3, 3]
  
    print(countSink(n, m, edgeFrom, edgeTo))
  
# This code is contributed by PranchalK

// C# program to count number if sink nodes
using System;
      
class GFG
{
  
// Return the number of Sink NOdes.
static int countSink(int n, int m, 
                     int []edgeFrom,
                     int []edgeTo)
{
    // Array for marking the non-sink node.
    int []mark = new int[n + 1];
  
    // Marking the non-sink node.
    for (int i = 0; i < m; i++)
        mark[edgeFrom[i]] = 1;
  
    // Counting the sink nodes.
    int count = 0;
    for (int i = 1; i <= n ; i++)
        if (mark[i] == 0)
            count++;
  
    return count;
}
  
// Driver Code
public static void Main(String[] args)
{
    int n = 4, m = 2;
    int []edgeFrom = { 2, 4 };
    int []edgeTo = { 3, 3 };
  
    Console.WriteLine(countSink(n, m, 
                      edgeFrom, edgeTo));
}
}
  
// This code is contributed by PrinciRaj1992

<script>
  
// Javascript program to count number if sink nodes
  
// Return the number of Sink NOdes.
function countSink(n, m, edgeFrom, edgeTo)
{
      
    // Array for marking the non-sink node.
    let mark = new Array(n + 1);
    for(let i = 0; i < n + 1; i++)
    {
        mark[i] = 0;
    }
      
    // Marking the non-sink node.
    for(let i = 0; i < m; i++)
        mark[edgeFrom[i]] = 1;
    
    // Counting the sink nodes.
    let count = 0;
    for(let i = 1; i <= n; i++)
        if (mark[i] == 0)
            count++;
    
    return count;
}
  
// Driver Code
let n = 4, m = 2;
let edgeFrom = [ 2, 4 ];
let edgeTo = [ 3, 3 ];
  
document.write(countSink(n, m, 
                         edgeFrom, edgeTo));
  
// This code is contributed by rag2127
  
</script>

Producción: 

2

Complejidad temporal: O(m + n) donde n es el número de Nodes ym es el número de aristas.

Artículo Relacionado:  
El Problema de la Celebridad

Este artículo es una contribución de Anuj Chauhan . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.