题目：

分析：图这块的题还是不会。

瞄了一眼题解，哦，可以当做宽搜来做一下子。

基本没优化，t了，：

#include<bits/stdc++.h> using namespace std; int m,n; vector<vector<int> > vv; int done[1000005]; int done2[1000005]; void bfs() { queue<int> q; q.push(1); while(!q.empty()) { memset(done2,0,sizeof(done2)); queue<int> qq; while(!q.empty()) { int c=q.front(); q.pop(); if(done[c]!=0) continue; done2[c]++; for(int i=0;i<vv[c].size();i++) { if(done[vv[c][i]]!=0) continue; qq.push(vv[c][i]); } } for(int i=1;i<=m;i++) done[i]=max(done[i],done2[i]); q=qq; } } int main() { memset(done,0,sizeof(done)); cin>>m>>n; vector<int> v; for(int i=0;i<=m;i++) vv.push_back(v); for(int i=0;i<n;i++) { int c1,c2; cin>>c1>>c2; if(c1==c2) continue; vv[c1].push_back(c2); vv[c2].push_back(c1); } bfs(); for(int i=1;i<=m;i++) cout<<done[i]<<endl; }

对构造图和宽度优先应该有了更深一步的理解了。

大佬题解：用每个相邻且层数比当前结点层数少一的点更新当前点的路径跳数即可。

我再用自己的话说明一下：就是在当前队列中要出列的点，（不允许重复入队列），一定是最短路径的点。其下一个点，如果没有入队列过，那么一定也是最短路径点。