六度空间
“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示。

图1 六度空间示意图
“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。
假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式:
输入第1行给出两个正整数,分别表示社交网络图的结点数N(1<N≤103,表示人数)、边数M(≤33×N,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。
输出格式:
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
输入样例:
1 2 3 4 5 6 7 8 9 10
| 10 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
|
输出样例:
1 2 3 4 5 6 7 8 9 10
| 1: 70.00% 2: 80.00% 3: 90.00% 4: 100.00% 5: 100.00% 6: 100.00% 7: 100.00% 8: 90.00% 9: 80.00% 10: 70.00%
|
题目分析
- 对每个节点,进行广度优先搜索
- 搜索过程中累计访问的节点数
- 需要记录”层”数,仅计算6层以内的节点数
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include <cstdio> #include <queue> #include <string.h> #define MAX 10001 using namespace std; int MGraph[MAX][MAX]; int visit[MAX] = { 0 }; void InitGraph( int n ) { for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ) MGraph[i][j] = 0; } void InsertEdge( int i, int j ) { MGraph[i][j] = 1; MGraph[j][i] = 1; } double BFS( int curNode, int n ) { queue<int> q; visit[curNode] = 1; q.push( curNode ); int count = 1; for( int level = 0; level < 6; level++ ) { vector<int> vec; while( !q.empty() ) { int node = q.front(); vec.push_back( node ); q.pop(); } for( int i = 0; i < vec.size(); i++ ) { int node = vec[i]; for( int i = 1; i <= n; i++ ) { if( !visit[i] && MGraph[node][i] == 1 ) { q.push( i ); visit[i] = 1; count++; } } } } double rate = (double)count / (double)n; return rate * 100.0; } int main() { int N, E; scanf( "%d%d", &N, &E ); InitGraph( N ); int a, b; for( int i = 0; i < E; i++ ) { scanf( "%d%d", &a, &b ); InsertEdge( a, b ); } for( int i = 1; i <= N; i++ ) { memset( visit, 0, sizeof( visit[0] ) * ( N + 1 ) ); double r = BFS( i, N ); printf( "%d: %.2lf%%\n", i, r ); } return 0; }
|