首页 > 试题广场 >

重要节点

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

数据范围:

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


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

输入

4 3
2 1
3 1
1 4

输出

2

说明

样例解释:重要节点是1,4。 
70% 通过,不知道卡在哪里啦,很奇怪,哪位大神能解答一下?


#coding:__utf-8__
import queue
def zhongyao_dian(n,m,lists):
    Number_count = 0
    S = [0 for _ in range(n)]
    T = [0 for _ in range(n)]
    matrix = [[0 for _ in range(n)]for _ in range(n)]
    graph = []
    for i in range(n):
        graph.append([])
    stack = queue.Queue(maxsize=n)

    for i in lists:
        if i[1] not in graph[i[0]-1]:
            graph[i[0]-1].append(i[1]-1)
    for i in range(n):
        stack.put(i)
        while not stack.empty():
            cur = stack.get()
            for j in graph[cur]:
                if matrix[i][j] == 0:
                    matrix[i][j] = 1
                    stack.put(j)
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == 1:
                S[i] += 1
                T[j] += 1
    for i in range(n):
        if T[i] - S[i] >0:
            Number_count += 1
    return Number_count
if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    lists = []
    for i in range(m):
        lists.append([int(i) for i in input().split()])
    quchong_list = []
    for i in lists:
        if i not in quchong_list:
            quchong_list.append(i)
    print(zhongyao_dian(n, len(quchong_list), quchong_list))

发表于 2019-04-21 19:17:52 回复(0)

问题信息

难度:
1条回答 1908浏览

热门推荐

通过挑战的用户

查看代码