首页 > 试题广场 >

重要节点

[编程题]重要节点

热度指数：1313 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一张有向图 G(V,E) ，所有的边都是有向边，对于图上的一个点 v ，从 v 出发可以到达的点的集合记为 S_v，特别地， v ∈ S_v，再定义一个点的集合 T_v：从T_v中的任意一个点出发，可以到达点 v ，特别地，v∈T_v简而言之，S_v是 v 能到的点的集合，而 T_v是能到 v 的点的集合。

对于一个点 v ，如果 T_v中的点数严格大于 S_v 中的点数，那么 v 就是一个重要节点，输入一张图，输出图中重要节点的个数

数据范围： $1 \le n,m \le 1000 \$ ， $1 \le u,v \le n \$

输入描述:

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

输出描述:

输出一个数，重要节点的个数

示例1

输入

输出

说明

样例解释：重要节点是1，4。

算法知识视频讲解

Python3

Oliver1234

我python用Floyd写会超时。。。所以还是BFS稳妥

最简单粗暴的方法，构建正反向图，分别对俩图BFS统计Sv和Tv的容量并比较。

n, m = map(int, input().split())
ds, dt = {}, {} # ds,dt分别记录正向图，反向图
for i in range(1, n+1):
    ds[i], dt[i] = set([i]), set([i])
for i in range(m):
    x, y = map(int, input().split())
    ds[x].add(y)
    dt[y].add(x)
def bfs(x,d): # 使用bfs
    res = 0
    q = [x]
    visited = [False]*(n+1)
    visited[x] = True
    while q:
        cur = q.pop(0)
        res += 1
        for nxt in d[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append(nxt)
    return res
cnt = 0
for i in range(1,n+1):
    if bfs(i,ds) < bfs(i,dt): cnt += 1
print(cnt)

发表于 2022-02-07 19:14:10 回复(0)