题意：n个点的无向完全图中删除m条边，问点s到其他点的最短路径长度
题解一：BFS遍历，最短路径长度为step的同时遍历（用需要删去的边），若未入队的点被遍历到的次数小于最短路径长度为step的点的个数，则该点入队；否则留在未扩展点中。 （复杂度不会分析，感觉好像是min（n,m）^2）
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <set> #include <vector> using namespace std; const int N=200000+10; vector<int>V[N]; int b[N],islef[N],Ans[N]; int S,st[N],h,h1,st1[N]; int n,m,lef[N],All; int mark[N],re[N],gs; void work() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)V[i].clear(); for (int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); V[u].push_back(v); V[v].push_back(u); } scanf("%d",&S); for (int i=1;i<=n;i++)if (i!=S)All++,lef[All]=i,islef[i]=1; h=1;st[1]=S; memset(b,0,sizeof b); memset(mark,0,sizeof mark); for (int step=1;;step++){ for (int i=1;i<=h;i++){ int u=st[i];gs=0; for (int j=0;j<int(V[u].size());j++)if (!mark[V[u][j]]){ b[V[u][j]]++;mark[V[u][j]]=1;gs++;re[gs]=V[u][j]; } for (int j=1;j<=gs;j++)mark[re[j]]=0; } for (int i=1;i<=All;i++)if (b[lef[i]]<h){ islef[lef[i]]=0;Ans[lef[i]]=step; } int Now=All;All=0;h=0; for (int i=1;i<=Now;i++)if (islef[lef[i]]){ All++;lef[All]=lef[i];b[lef[i]]=0; }else h++,st[h]=lef[i]; if (h==0){ for (int i=1;i<=All;i++)Ans[lef[i]]=-1; break; } } int Flag=0; for (int i=1;i<=n;i++)if (i!=S){ if (!Flag){Flag=1;}else printf(" "); printf("%d",Ans[i]); } puts(""); } int main() { //freopen("1.txt","r",stdin); int Case;scanf("%d",&Case); while (Case--)work(); return 0; }题解二：当n>m+1时，最短路长度要么是1，要么是2。因为有长度为1的点可以作为跳板，总能遍历剩下的点，此时只要搜一下与S相连的点即可；
当n<=m+1时，直接bfs暴力
