> 백엔드 개발 > C++ > 본문

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

WBOY
풀어 주다: 2023-09-01 19:25:05
앞으로
503명이 탐색했습니다.

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

在本文中,我们将描述解决图中汇节点数量的重要信息。在这个问题中,我们有一个有 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;
}
로그인 후 복사

输出

2
로그인 후 복사

上述代码说明

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

结论

在本文中,我们使用集合的帮助解决了 O(N) 时间复杂度中查找图中存在的汇聚节点数量的问题。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。

위 내용은 使用C++找到图中的汇节点的数量의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!