一、题目概述

给定一个包含 $n$ 个城市的无向图，城市编号为 $1 \sim n$，城市之间通过 $m$ 条无向道路相连，所有道路的长度均为 1。
定义一个城市的繁华度为该城市连接的道路数量（即节点的度数）。

将所有城市的繁华度取出并去重后，从小到大排序，得到序列$$a_1, a_2, \dots, a_k$$

其中，繁华度等于 $a_i$​ 的城市被称为 iii 级城市，且 $k$k 级城市为最高级城市。

对于每一个城市 $x$，需要计算：
从城市 x 出发，到达任意一个“级别严格高于自身”的城市的最短路径长度。
如果无法到达任何更高级城市，则输出 $-1$。

最终需要输出一个长度为 $n$ 的数组，第 $x$ 个数表示城市 $x$ 的答案。

二、思路分析

求最短路径，第一反应就是用BFS，用暴力方法去解决这道题会发现需要每个节点都bfs一遍，从小“繁华度”的城市到任意更高级别的“繁华度”的城市就弹出，然后把dis记录下来，这个dis就是该点到更高级别的最短路径。然而这是一个O(n^2)级别的算法，很显然在这道题是行不通的。

是否存在一个复杂度更低的算法，这里引入多源bfs来解决这道题。通过正难则反的原理，我们从高繁华度城市向低繁华度城市遍历，将同等级繁华度的城市绑定到一个队列中，这样就可以仅用√m*(n+m)的复杂度就能解决问题

三、复杂度分析

这是一个O(√m*(n+m))级别的算法，能通过这道题

四、参考代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n+1);
	vector<int> deg(n+1);
	
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}//初始化图和“繁华度” 
	
	map<int, deque<int>> mp;
	for(int i = 1; i <=n; i++)
	{
		mp[deg[i]].push_back(i);
	}/*划分繁华度等级，将对应的点放进mp中 */ 
	
	vector<int> dis(n+1,1e9);
	vector<int> ans(n+1);
	//逆序多源bfs 
	for(map<int,deque<int>>::reverse_iterator it = mp.rbegin();
	it != mp.rend(); ++it){
		int x = it->first;
		deque<int> &q = it->second;
		for(auto &i:q)
		{
			if(dis[i] > 1e8) dis[i] = -1;
			ans[i] = dis[i];
			dis[i] = 0;
		}/*将未bfs到的点标记为-1，并赋值给ans，
		然后以这个繁华度为0距离点开始下一轮bfs */
		
		while(!q.empty())
		{
			auto u = q.front();
			q.pop_front();
			for(auto v:adj[u])
			{
				if(x <= deg[v]) continue;
				if(dis[u] + 1 < dis[v])
				{
					dis[v] = dis[u] + 1;
					q.push_back(v);
				}
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		cout << ans[i] << " ";
	}
	cout << "\n";
}