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

小世界现象（又称小世界效应），也称六度分隔理论（英文：Six Degrees of Separation）。假设世界上所有互不相识的人只需要很少中间人就能建立起联系。后来1967年哈佛大学的心理学教授斯坦利·米尔格拉姆根据这概念做过一次连锁信实验，尝试证明平均只需要5个中间人就可以联系任何两个互不相识的美国人。 NowCoder最近获得了社交网站Footbook的好友关系资料，请你帮忙分析一下某两个用户之间至少需要几个中间人才能建立联系？输入描述: 输入第一行是一个整数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)。输出描述: 对于每组待分析的用户，输出用户A至少需要通过几个中间人才能认识用户B。如果A无论如何也无法认识B，输出“Sorry”。输入例子: 251 0 1 0 10 1 1 1 01 1 1 0 00 1 0 1 01 0 0 0 131 22 43 561 1 0 0 1 01 1 0 1 0 10 0 1 0 0 10 1 0 1 0 11 0 0 0 1 00 1 1 1 0 142 33 65 14 2 输出例子: 1011021

还没有评论

举报纠错

切换

1 个答案

广度搜索 #include #include #include using namespace std; struct node { int cur; int num; }; int littleworld(int from , int to, vector< vector > Map, int n) { int i; vector mid(n); vector flag(n); queue Q; node first; first.cur = from; first.num = 0; Q.push(first); for(i=0;i>totle; while(totle--){ cin>>n; vector< vector > Map(n,vector(n)); for(i=0;i>Map[i][j]; } } cin>>m; int from,to; for(i=0;i> from >> to; int res = littleworld(from-1,to-1, Map,n); if(res == -1) cout << "Sorry" << endl; else cout << res << endl; } } return 0; }

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目