“六度空间”理论又称作“六度分隔”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。 输入格式: 输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103 ,表示人数)、边数M(≤33,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。 输出格式: 对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
时间: 2024-03-17 08:40:37 浏览: 28
以下是Python代码实现:
```python
import queue
def bfs(graph, n, start):
visited = [False] * (n + 1)
q = queue.Queue()
q.put((start, 0))
visited[start] = True
count = 0
while not q.empty():
u, d = q.get()
if d > 6:
break
count += 1
for v in graph[u]:
if not visited[v]:
visited[v] = True
q.put((v, d + 1))
return count / n * 100
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
for i in range(1, n + 1):
print("%d: %.2f%%" % (i, bfs(graph, n, i)))
```
输入时,先输入节点数N和边数M,然后输入M条边,每条边输入两个节点编号。代码通过BFS遍历每个节点,计算每个节点到其他节点的距离,统计距离不超过6的节点数量,最终输出占总节点数的百分比。