社交网络图中结点的“重要性”计算

题目描述

输入

输出

输入样例1 

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9

输出样例1

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35

AC代码

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>using namespace std;// 使用BFS计算从某个结点出发到其他所有结点的最短路径和
double calculate_closeness(int start, int N, const vector<vector<int>> &adj)
{vector<int> dist(N + 1, -1); // 初始化距离为-1，表示未访问queue<int> q;q.push(start);dist[start] = 0;int total_distance = 0;int reachable_nodes = 0;// BFS 计算距离while (!q.empty()){int node = q.front();q.pop();reachable_nodes++;for (int neighbor : adj[node]){if (dist[neighbor] == -1){ // 如果未访问过dist[neighbor] = dist[node] + 1;total_distance += dist[neighbor];q.push(neighbor);}}}// 如果该结点是非连通图中的一个孤立结点，紧密度中心性为0if (reachable_nodes < N)return 0.0;// 紧密度中心性定义为 1 / 平均距离return (reachable_nodes - 1) / static_cast<double>(total_distance);
}int main()
{int N, M;cin >> N >> M;vector<vector<int>> adj(N + 1); // 邻接表存储图for (int i = 0; i < M; i++){int u, v;cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}int K;cin >> K;vector<int> nodes_to_calculate(K);for (int i = 0; i < K; i++){cin >> nodes_to_calculate[i];}// 对每个需要计算的结点，输出其紧密度中心性for (int node : nodes_to_calculate){double closeness = calculate_closeness(node, N, adj);cout << "Cc(" << node << ")=" << fixed << setprecision(2) << closeness << endl;}return 0;
}