使用 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

以上程式碼的解釋

在此程式碼中，我們將遍歷向量 edges 並將對中的第一個元素插入到集合中。它只保留不同的元素，因此現在我們將從節點總數中減去集合的特定大小。上面顯示的程式的時間複雜度為 **O(N)**，其中 N 代表圖中存在的邊數。

結論

在本文中，我們使用集合解決了在 O(N) 時間複雜度內查詢圖中匯點數量的問題。我們還學習了此問題的 C++ 程式以及解決此問題的完整方法。我們可以用其他語言（如 C、Java、Python 等）編寫相同的程式。希望本文對您有所幫助。

更新於： 2021-11-24

236 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告