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

WBOY

发布时间：2023-09-01 19:25:05

737人浏览过

来源于tutorialspoint

转载

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

输出

上述代码说明

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

宠物商店

目前，PetShop已经从最初的2.0、3.0等版本，发展到了最新的4.0版本。PetShop 4.0使用ASP.NET 2.0技术开发，其中加入了众多新增特性，因此，在性能、代码数量、可扩展性等方面有了重大改善。可以说，学习PetShop 4.0是深入掌握ASP.NET 2.0技术的捷径。本节将引领读者逐步了解PetShop 4.0的方方面面，包括应用程序安装、功能和用户界面简介、解决方案和体系

下载

结论

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

立即学习“C++免费学习笔记（深入）”；

C++移动语义深度剖析：右值引用与完美转发避坑指南【性能关键点】

如何用Google Test为c++代码编写单元测试？ (基本断言入门)

如何在CLion中高效调试c++代码？ (条件断点与变量可视化)

c++中如何使用std::none_of算法_c++确保容器无满足条件元素【详解】

c++如何与QML进行数据交互？ (Qt开发实践)

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

c语言 Python Java

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：在C++中实现strtok()函数下一篇：使用C++移除给定数字中的重复数字

作者最新文章

玩转夸克浏览器的AI搜索模式_夸克AI搜索新手入门操作指南

2025-10-20 09:50

夸克浏览器AI搜索最新版教学_探索夸克AI搜索的隐藏功能

2025-10-24 20:48

夸克浏览器怎么用AI搜索_夸克AI搜索正确提问方式教学

2025-10-25 23:12

微信朋友圈怎么设置定时发布微信朋友圈定时发送图文教程

2026-01-02 09:14

微信朋友圈怎么定时发送微信朋友圈定时发布设置方法【教程】

2026-01-06 09:59

苹果手机怎么定时发朋友圈 iPhone微信朋友圈自动发布方法【步骤】

2026-01-08 11:11

微信朋友圈能定时发送吗微信朋友圈定时发送功能开启方法

2026-01-09 08:15

微信朋友圈草稿箱怎么用微信朋友圈定时发送隐藏技巧

2026-01-10 08:41

微信朋友圈定时发送是真的吗微信朋友圈预约发布实现方法

2026-01-15 10:19

微信定时发朋友圈怎么弄微信朋友圈自动推送设置流程

2026-01-21 04:27

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PC软件

相关专题

python开发工具

php中文网为大家提供各种python开发工具，好的开发工具，可帮助开发者攻克编程学习中的基础障碍，理解每一行源代码在程序执行时在计算机中的过程。php中文网还为大家带来python相关课程以及相关文章等内容，供大家免费下载使用。

772

2023.06.15

python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章，大家可以免费的下载体验。

661

2023.07.20

python能做什么

python能做的有：可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

764

2023.07.25

format在python中的用法

Python中的format是一种字符串格式化方法，用于将变量或值插入到字符串中的占位符位置。通过format方法，我们可以动态地构建字符串，使其包含不同值。php中文网给大家带来了相关的教程以及文章，欢迎大家前来阅读学习。

679

2023.07.31

python教程

Python已成为一门网红语言，即使是在非编程开发者当中，也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章，大家可以免费体验学习。

1365

2023.08.03

python环境变量的配置

Python是一种流行的编程语言，被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后，我们需要配置环境变量，以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

569

2023.08.04

python eval

eval函数是Python中一个非常强大的函数，它可以将字符串作为Python代码进行执行，实现动态编程的效果。然而，由于其潜在的安全风险和性能问题，需要谨慎使用。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

579

2023.08.04

scratch和python区别

scratch和python的区别：1、scratch是一种专为初学者设计的图形化编程语言，python是一种文本编程语言；2、scratch使用的是基于积木的编程语法，python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容，供大家免费下载体验。

730

2023.08.11