C++を使用してグラフ内のシンクノードの数を見つける

この記事では、グラフ内のシンクノードの数を解決するための重要な情報について説明します。この問題では、N個のノード（1からN）とM個のエッジを持つ有向非巡回グラフがあります。目標は、指定されたグラフにシンクノードがいくつあるかを見つけることです。シンクノードは、出力エッジを生成しないノードです。簡単な例を次に示します-

Input : n = 4, m = 2

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

解決策を見つけるための簡単なアプローチ

このアプローチでは、グラフのエッジを調べ、エッジの元となるセット内の個別の要素をプッシュしてから、存在するノードの総数からセットのサイズを減算します。

例

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

出力

2

上記のコードの説明

このコードでは、ベクトルエッジをトラバースし、ペアの最初の要素をセットに挿入します。個別の要素のみを保持するため、ノードの総数からセットの特定のサイズを減算します。上に示したプログラムは、 O（N）の時間計算量を持っています ここで、Nはグラフに存在するエッジの数を表します。

結論

この記事では、セットの助けを借りて、グラフのO（N）時間計算量に存在するシンクノードの数を見つける問題を解決しました。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチについても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。