题意 ：N个点的完全图，删除M条边，问s到其他点的最短路是多少
bfs下，用set存点，若uv无边，则 距离加1切把v入队
#include<iostream> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<cstring> #include<string> #include<set> #include<map> using namespace std; typedef long long LL; const int maxn = 2e5 + 10; set<int> G[maxn]; set<int> p; int n,m; int d[maxn]; void solve() { int t; scanf("%d",&t); while(t--) { p.clear(); scanf("%d%d",&n,&m); for(int i =1;i<=n;i++) { p.insert(i); G[i].clear(); d[i] = -1; } for(int i = 0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); G[u].insert(v); G[v].insert(u); } int s; scanf("%d",&s); p.erase(s); d[s] = 0; queue<int> q; q.push(s); while(!q.empty()) { int t = q.front(); q.pop(); vector<int> v; for(auto it = p.begin();it!=p.end();it++) { if(!G[t].count(*it)) { d[*it] = d[t] +1; q.push(*it); v.push_back(*it); } } for(int i = 0;i<v.size();i++) { p.erase(v[i]); } } bool flag = true; for(int i = 1;i<=n;i++) { if(i==s)continue; if(flag) { printf("%d",d[i]); flag = false; }else { printf(" %d",d[i]); } } printf("\n"); } } int main() { solve(); return 0; }