J题 | 终于再见

解题思路：

对于所有繁荣度为a的城市，以它们为起点bfs遍历所有繁荣度小于它们的城市，可以得到那些城市到繁荣度为a的城市的距离，这可能会是答案，但也许存在更短的路径。

假设有所有城市的繁荣度去重后有k种，那进行k次bfs遍历，在更新路径的时候和原答案比较，最后可以得到所有正确答案，时间复杂度为O(k×(n+m))，会不会太大了点。但对于本题，可以证明繁荣度的种数最多为√m种，因此时间复杂度为O(√m×(n+m))。

示例代码：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e5+5;

int n, m;
vector<int> arr[N];//邻接表存图
int prps[N];//繁荣度
bool vis[N]//bfs时用于标记遍历过的点;
int dis[N], ans[N]//dis数组：bfs时更新距离，ans数组：记录最短路径

vector<pii> all;//first:繁荣度  second:城市序号
//用来记录所有不同繁荣度和对应城市序号

void solve() {
	cin >> n >> m;

	for (int i = 1, u, v; i <= m; i++) {//输入，建图，不断更新每座城市繁荣度
		cin >> u >> v;
		arr[u].push_back(v);
		arr[v].push_back(u);
		prps[u]++;
		prps[v]++;
	}

	for (int i = 1; i <= n; i++)
		all.push_back({prps[i], i}),
		              ans[i] = N;

	sort(all.begin(), all.end());//排序，繁荣度大的靠后

	while (all.size()) {//多源bfs，本质是把所有不同繁荣度的城市都作为起点遍历一次
		int now_prps = all.back().first;//当前以all_prps繁荣度的城市为起点遍历

		queue<int> q;
		while (all.size() && all.back().first == now_prps) {//所有繁荣度为all_prps的城市添加到队列后开启一轮bfs
			q.push(all.back().second);
			vis[all.back().second] = 1;
			all.pop_back();
		}

		for (int i = 1; i <= n; i++)
			vis[i] = 0, dis[i] = 0;

		while (q.size()) {
			int now = q.front();
			q.pop();

			for (int nxt : arr[now]) {
				if (vis[nxt] || prps[nxt] >= now_prps) continue;

				dis[nxt] = dis[now] + 1;
				ans[nxt] = min(ans[nxt], dis[nxt]);
				vis[nxt] = 1;
				q.push(nxt);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (ans[i] < N) cout << ans[i] << " ";
		else cout << "-1 ";
	}
}

signed main() {
	int T = 1;
	//cin >> T;
	while (T--)
		solve();

	return 0;
}