数据结构与算法题目集7-36——社交网络图中结点的“重要性”计算

我的数据结构与算法题目集代码仓：https://github.com/617076674/Data-structure-and-algorithm-topic-set

原题链接：https://pintia.cn/problem-sets/15/problems/863

题目描述：

知识点：无权图的最短路径

思路：SPFA算法

期望时间复杂度是O(kM)，其中k是一个常数，在很多情况下k不超过2，可见这个算法异常高效，并且经常性地优于堆优化的Dijkstra算法。

C++代码：

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int N, M, INF = 1000000000;
vector<int> graph[10001];
int d[10001], countInq[10001];
bool inq[10001];

bool spfa(int s);

int main(){
	scanf("%d %d", &N, &M);
	for(int i = 0; i < M; i++){
		int v1, v2;
		scanf("%d %d", &v1, &v2);
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	int K;
	scanf("%d", &K);
	for(int i = 0; i < K; i++){
		int query;
		scanf("%d", &query);
		bool flag = spfa(query);
		if(!flag){
			printf("Cc(%d)=0.00\n", query);
		}else{
			int total = 0;
			for(int i = 1; i <= N; i++){
				total += d[i];
			}
			printf("Cc(%d)=%.2f\n", query, (N - 1) * 1.0 / total);
		}
	}
	return 0;
}

bool spfa(int s){
	fill(d + 1, d + N + 1, INF);
	fill(countInq + 1, countInq + N + 1, 0);
	fill(inq + 1, inq + N + 1, false);
	d[s] = 0;
	queue<int> q;
	q.push(s);
	countInq[s]++;
	inq[s] = true;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		inq[u] = false;
		for(int i = 0; i < graph[u].size(); i++){
			int v = graph[u][i];
			int len = 1;
			if(d[u] + len < d[v]){
				d[v] = d[u] + len;
				if(!inq[v]){
					q.push(v);
					countInq[v]++;
					inq[v] = true;
					if(countInq[v] > N - 1){
						return false;
					}
				}
			}
		}
	}
	return true;
}

C++解题报告：