Ermitteln Sie mit C++ die Anzahl der Senkenknoten in einem Diagramm

In diesem Artikel beschreiben wir die wichtigen Informationen, um die Anzahl der Senkenknoten in einem Diagramm zu ermitteln. In diesem Problem haben wir einen gerichteten azyklischen Graphen mit N Knoten (1 bis N) und M Kanten. Das Ziel besteht darin, herauszufinden, wie viele Senkenknoten es in einem bestimmten Diagramm gibt. Ein Senkenknoten ist ein Knoten, der keine ausgehenden Kanten erzeugt. Hier ist ein einfaches Beispiel –

Input : n = 4, m = 2

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

Einfache Möglichkeit, die Lösung zu finden

Bei dieser Methode durchlaufen wir die Kanten des Diagramms, schieben verschiedene Elemente aus der Menge, auf die die Kante zeigt, hinein und subtrahieren dann die Größe der Menge Gesamtzahl der vorhandenen Knoten.

Beispiel

#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;
}

Ausgabe

2

Obenige Codebeschreibung

In diesem Code iterieren wir über die Vektorkanten und fügen das erste Element des Paares in die Menge ein. Es behält nur unterschiedliche Elemente bei, daher subtrahieren wir jetzt die spezifische Größe der Sammlung von der Gesamtzahl der Knoten. Die zeitliche Komplexität des oben gezeigten Programms beträgt O(N), wobei N die Anzahl der im Diagramm vorhandenen Kanten darstellt.

Fazit

In diesem Artikel haben wir das Problem gelöst, die Anzahl der in einem Diagramm in O(N)-Zeitkomplexität vorhandenen Senkenknoten mithilfe von Mengen zu ermitteln. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Methode zur Lösung dieses Problems gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonErmitteln Sie mit C++ die Anzahl der Senkenknoten in einem Diagramm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!