Trouver le nombre de nœuds récepteurs dans un graphique en utilisant C++

Dans cet article, nous décrirons les informations importantes pour résoudre le nombre de nœuds récepteurs dans un graphique. Dans ce problème, nous avons un graphe acyclique orienté avec N nœuds (1 à N) et M arêtes. Le but est de savoir combien de nœuds récepteurs il y a dans un graphe donné. Un nœud récepteur est un nœud qui ne génère aucun front sortant. Voici un exemple simple -

Input : n = 4, m = 2

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

Un moyen simple de trouver la solution

Dans cette méthode, nous allons parcourir les bords du graphique, y pousser différents éléments de l'ensemble pointé par le bord, puis soustraire la taille de l'ensemble. nombre total de nœuds présents.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 4; // number of nodes.
    int m = 2; // number of edges.
    vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
    set<int> s;
    for(int i = 0; i < m; i++){
        s.insert(edges[i].first); // will keep value of
                               // distinct node from which edges are going out.
    }
    cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
    return 0;
}

Sortie

2

Description du code ci-dessus

Dans ce code, nous allons parcourir les bords du vecteur et insérer le premier élément de la paire dans l'ensemble. Il ne conserve que des éléments distincts, nous allons donc maintenant soustraire la taille spécifique de la collection du nombre total de nœuds. La complexité temporelle du programme présenté ci-dessus est O(N), où N représente le nombre d'arêtes présentes dans le graphique.

Conclusion

Dans cet article, nous avons résolu le problème de trouver le nombre de nœuds récepteurs présents dans un graphe en complexité temporelle O(N) à l'aide d'ensembles. Nous avons également appris un programme C++ pour résoudre ce problème et une méthode complète pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!