“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比 多组数据,每组数据m+1行。第一行有两个数字n和m,代表有n个人和m组朋友关系。n个人的编号为1到n。第二行到第m+1行每行包括两个数字a和b,代表这两个人互相认识。当n和m都等于0时,输入结束。 每组数据输出n行,对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
时间: 2024-02-11 09:08:46 浏览: 93
好的,那我们可以按照题目要求,使用C++来解决这个问题。具体来说,你需要对原有的代码进行一些修改,以便能够求解每个节点的“六度空间”百分比。
下面是修改后的代码,其中我添加了一些注释,希望能够帮助你更好地理解:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#include <iomanip>
using namespace std;
const int MAXN = 10000;
const int INF = 1e9;
vector<int> G[MAXN+5];
int d[MAXN+5];
bool used[MAXN+5];
void bfs(int s) {
queue<int> q;
q.push(s);
d[s] = 0;
used[s] = true;
while(!q.empty()) {
int v = q.front(); q.pop();
for(int i=0; i<G[v].size(); i++) {
int u = G[v][i];
if(!used[u]) {
used[u] = true;
d[u] = d[v] + 1;
q.push(u);
}
}
}
}
int main() {
int n, m;
while(cin >> n >> m && n > 0 && m > 0) {
// 初始化
memset(d, 0, sizeof(d));
memset(used, false, sizeof(used));
for(int i=1; i<=n; i++) G[i].clear();
// 构建无向图
for(int i=0; i<m; i++) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
// 求解每个节点的“六度空间”百分比
for(int i=1; i<=n; i++) {
// 求解最短路径
bfs(i);
// 统计符合条件的节点数量
int cnt = 0;
for(int j=1; j<=n; j++) {
if(d[j] <= 6) cnt++;
}
// 输出结果
double ans = (double)cnt / n * 100;
cout << fixed << setprecision(2) << i << ": " << ans << "%" << endl;
}
}
return 0;
}
```
这段代码中,我们首先通过输入来获取网络图的信息,然后对每个节点依次进行求解,得到与该节点距离不超过6的节点数。最后,我们将得到的结果按照要求输出即可。
需要注意的是,题目中要求输出的百分比需要保留两位小数,因此我们使用了 `fixed` 和 `setprecision` 来控制输出格式。另外,题目中并没有说明节点数和边数的范围,因此我们需要根据实际情况来确定数组的大小,避免越界等错误。
阅读全文