【免费】解题思路20资源-CSDN文库

需积分: 0 185 浏览量 2022-08-08 18:02:32 上传评论收藏 201KB DOCX 举报

资源详情

资源评论

资源推荐

小世界现象

1 / 5

小世界现象

1 题目描述

小世界现象（又称小世界效应），也称六度分隔理论（英文：Six Degrees of Separation）。

假设世界上所有互不相识的人只需要很少中间人就能建立起联系。后来 1967 年哈佛大学的心理学

教授斯坦利·米尔格拉姆根据这概念做过一次连锁信实验，尝试证明平均只需要 5 个中间人就可

以联系任何两个互不相识的美国人。NowCoder 最近获得了社交网站 Footbook 的好友关系资料，

请你帮忙分析一下某两个用户之间至少需要几个中间人才能建立联系？

1.1 输入描述:

输入第一行是一个整数 t，表示紧接着有 t 组数据。每组数据包含两部分：第一部分是好友关

系资料；第二部分是待分析的用户数据。

好友资料部分第一行包含一个整数 n(5≤n≤50)，表示有 n 个用户，用户 id 用 1->n 表示。

紧接着是一个只包含 0 和 1 的 n×n 矩阵，其中第 y 行第 x 列的值表示 id 是 y 的用户是否是 id

为 x 的用户的好友（1 代表是，0 代表不是）。假设好友关系是相互的，即 A 是 B 的好友意味着 B

也是 A 的好友。

待分析的用户数据第一行包含一个整数 m，紧接着有 m 行用户组数据。每组有两个用户 ID，A

和 B(1≤A，B≤n，A!=B)。

1.2 输出描述:

对于每组待分析的用户，输出用户 A 至少需要通过几个中间人才能认识用户 B。如果 A 无论如

何也无法认识 B，输出“Sorry”。

1.3 输入例子:

2

5

1 0 1 0 1

0 1 1 1 0

1 1 1 0 0

0 1 0 1 0

1 0 0 0 1

3

1 2

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

评论0

内容反馈

嘻嘻哒的小兔子

粉丝: 26
资源: 321

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip