使用 C++ 查找图中汇点的数量

在本文中，我们将介绍有关解决图中汇点数量的重要信息。在这个问题中，我们有一个具有 N 个节点（1 到 N）和 M 条边的有向无环图。目标是找到给定图中存在多少个汇点。汇点是一个不产生任何出边的节点。以下是一个简单的示例：

Input : n = 4, m = 2

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

查找解决方案的简单方法

在这种方法中，我们将遍历图的边，将来自边的不同元素推入集合中，然后用节点总数减去集合的大小。

示例

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

2

以上代码的解释

在此代码中，我们将遍历向量 edges 并将对中的第一个元素插入到集合中。它只保留不同的元素，因此现在我们将从节点总数中减去集合的特定大小。上面显示的程序的时间复杂度为 **O(N)**，其中 N 代表图中存在的边数。

结论

在本文中，我们使用集合解决了在 O(N) 时间复杂度内查找图中汇点数量的问题。我们还学习了此问题的 C++ 程序以及解决此问题的完整方法。我们可以用其他语言（如 C、Java、Python 等）编写相同的程序。希望本文对您有所帮助。

更新于： 2021-11-24

236 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告