使用 C++ 查找图中的汇节点数
在本文中,我们将描述有关解决图中汇节点数量的重要信息。在这个问题中,我们有一个有 N 个节点(1 到 N)和 M 个边的有向无环图。目标是找出给定图中有多少个汇节点。汇节点是不产生任何出边的节点。所以这是一个简单的例子 -
Input : n = 4, m = 2Edges[] = {{2, 3}, {4, 3}}Output : 2
寻找解决方案的简单方法
在这种方法中,我们将遍历图的边,将边缘所在的集合中的不同元素推送出去,然后用存在的节点总数减去集合的大小。
示例
#include <bits/stdc++.h>using namespace std;int main(){ int n = 4; // 节点数。 int m = 2; // 边数。 vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // 从第一到第二的边缘。 set<int> s; for(int i = 0; i < m; i++){ s.insert(edges[i].first); // 将保持价值 // 不同的节点从哪个边缘出去。 } cout << n - s.size(); // 答案是节点总数 - 非汇节点数。 return 0; }
输出结果
2
以上代码说明
在这段代码中,我们将遍历向量边并将该对的第一个元素插入到一个集合中。它只保留不同的元素,所以现在我们将从节点总数中减去集合的特定大小。上面显示的程序的时间复杂度为O(N),其中 N 代表图中存在的边数。
结论
在本文中,我们O(N)使用集合的帮助解决了查找图时间复杂度中存在的汇节点数的问题。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。希望这篇文章对您有所帮助。