首页 > 试题广场 >

重要节点

[编程题]重要节点
  • 热度指数：1288 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出一张有向图 G(V,E) ，所有的边都是有向边，对于图上的一个点 v ，从 v 出发可以到达的点的集合记为 Sv ，特别地， v ∈ Sv，再定义一个点的集合 Tv：从Tv中的任意一个点出发，可以到达点 v ，特别地，v∈Tv简而言之，Sv是 v 能到的点的集合，而 Tv 是能到 v 的点的集合。
对于一个点 v ，如果 Tv中的点数严格大于 Sv 中的点数，那么 v 就是一个重要节点，输入一张图，输出图中重要节点的个数

数据范围： ，

输入描述:
第一行输入两个数 n,m ，分别表示点数和边数。
接下来 m 行，每行两个数 u ， v 。表示一条从 u 到 v 的有向边，输入中可能存在重边和自环。


输出描述:
输出一个数，重要节点的个数
示例1

输入

4 3
2 1
3 1
1 4

输出

2

说明

样例解释：重要节点是1，4。
算法知识视频讲解
开通博客
头像 秦时明月2022
发表于 2022-08-19 10:35:17
解题思路 1.使用广度优先搜索分别计算当前节点的S值和T值,S值即为以当前节点i为起始点所有能访问的节点数,T值则为对所有节点执行广度优先搜索,当前节点i被访问的次数; 代码 #include <bits/stdc++.h> using namespace std; int main 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-01-08 10:58:30
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { // 邻接节点 private 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

查找
难度：
10条回答 1903浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号