首页 > 试题广场 >

第一题

[编程题]第一题
  • 热度指数:14252 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
该题的目的是要你统计图的连通分支数。

输入描述:
每个输入文件包含若干行,每行两个整数i,j,表示节点i和j之间存在一条边。
(请使用循环输入,可以参考该网址:https://www.nowcoder.com/discuss/276)


输出描述:
输出每个图的联通分支数。
示例1

输入

1 4
4 3
5 5

输出

2
import sys

nodes = set()
edges = []

for line in sys.stdin:
    start, end = list(map(int, line.strip().split()))
    nodes.add(start)
    nodes.add(end)
    edges.append([start, end])
    edges.append([end, start])

nodes = list(nodes)
adjusts = {}
isvisited = {}
for node in nodes:
    adjusts[node] = []
    isvisited[node] = False

for start, end in edges:
    if start == end:
        pass
    else:
        adjusts[start].append(end)

count = 0
for node in nodes:
    if not isvisited[node]:
        count += 1
        queue = [node]
        while len(queue) > 0:
            cur = queue[0]
            queue.pop(0)
            for next_node in adjusts[cur]:
                if not isvisited[next_node]:
                    queue.append(next_node)
                    isvisited[next_node] = True

print(count)

发表于 2024-03-20 23:21:25 回复(0)