在本文中，我們將描述解決圖中匯節點數量的重要資訊。在這個問題中，我們有一個有 N 個節點（1 到 N）和 M 個邊的有向無環圖。目標是找出給定圖中有多少個匯節點。匯聚節點是不產生任何傳出邊的節點。這是一個簡單的例子-
Input : n = 4, m = 2
Edges[] = {{2, 3}, {4, 3}}
Output : 2登入後複製
尋找解決方案的簡單方法
在這個方法中，我們將遍歷圖的邊，將邊所指向的集合中的不同元素推入其中，然後減去集合的大小存在的節點總數。
範例
#include
using namespace std;
int main(){
int n = 4; // number of nodes.
int m = 2; // number of edges.
vector> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
set 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;
}
登入後複製
輸出
上述程式碼說明
在這段程式碼中，我們將遍歷向量邊並將該對的第一個元素插入到集合中。它只保留不同的元素，所以現在我們將從節點總數中減去集合的具體大小。上面顯示的程式的時間複雜度為 O(N)，其中 N 代表圖中存在的邊數。
結論
在本文中，我們使用集合的幫助解決了 O(N) 時間複雜度中尋找圖中存在的匯聚節點數量的問題。我們也學習了解決這個問題的C 程式以及解決這個問題的完整方法。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。希望這篇文章對您有幫助。
以上是使用C++找到圖中的匯節點的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！
