使用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等語言來寫同樣的程式。希望這篇文章對您有幫助。

以上是使用C++找到圖中的匯節點的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！