Find the number of sink nodes in a graph using C++

In this article, we will describe important information for solving the number of sink nodes in a graph. In this problem, we have a directed acyclic graph with N nodes (1 to N) and M edges. The goal is to find out how many sink nodes there are in a given graph. A sink node is a node that does not generate any outgoing edges. Here is a simple example -

Input : n = 4, m = 2

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

Easy way to find the solution

In this approach we will traverse the edges of the graph pushing different elements from the set pointed by the edge into it and then subtract the size of the set from the total number of nodes present.

Example

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

Output

2

Description of the above code

In this code, we will iterate over the vector edges and add the first of the pair Elements are inserted into the collection. It only keeps distinct elements, so now we will subtract the specific size of the collection from the total number of nodes. The program shown above has a time complexity of O(N), where N represents the number of edges present in the graph.

Conclusion

In this article, we solved the problem of finding the number of sink nodes present in a graph in O(N) time complexity using the help of sets. We also learned a C program to solve this problem and a complete method to solve this problem. We can write the same program in other languages ​​such as C, java, python and other languages. Hope this article is helpful to you.

The above is the detailed content of Find the number of sink nodes in a graph using C++. For more information, please follow other related articles on the PHP Chinese website!