在本文中，我们将描述解决图中汇节点数量的重要信息。在这个问题中，我们有一个有 N 个节点（1 到 N）和 M 个边的有向无环图。目标是找出给定图中有多少个汇节点。汇聚节点是不产生任何传出边的节点。这是一个简单的例子 –
Input : n = 4, m = 2Edges[] = {{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<pair> 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;}
输出
2
上述代码说明
在这段代码中，我们将遍历向量边并将该对的第一个元素插入到集合中。它只保留不同的元素，所以现在我们将从节点总数中减去集合的具体大小。上面显示的程序的时间复杂度为 O(N)，其中 N 代表图中存在的边数。
结论
在本文中，我们使用集合的帮助解决了 O(N) 时间复杂度中查找图中存在的汇聚节点数量的问题。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。
立即学习“C++免费学习笔记（深入）”；
以上就是使用C++找到图中的汇节点的数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444242.html
微信扫一扫 
支付宝扫一扫 
