题意：给你n个点，m条无向边，问你这n个点构成的完全图，不用那m条边，由一个s出现的单源最短路
解题思路：首先，暴力建图不行，点太多，那么我们就按照它的规则来，把m条边建好，但是建的这个图表示不走的方法，然后我们需要用一个东西来保存去除这些直接相连的边的其它点，用set
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<cstdio>
using namespace std;
const int maxn=200500;
const int inf=0x3f3f3f3f;
struct Edge
{
int next;
int to;
}edge[maxn];
int head[maxn];
int visit[maxn];
int dist[maxn];
int cnt;
int n,m;
int start;
set<int>s;
void add(int u,int v)
{
edge[cnt].next=head[u];edge[cnt].to=v;head[u]=cnt++;
}
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
void bfs(int u)
{
fill(dist+1,dist+1+n,inf);
queue<int>q;
q.push(u);
set<int>s1,s2;//s2保存未拓展的点，既还没有到达可能由其它点中转的点；
dist[u]=0;
for(int i=1;i<=n;i++)
if(i!=u)
s1.insert(i);//先把所有点加入
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!s1.count(v))//如果这个点被直接连边，那么这条边不算
continue;
s1.erase(v);
s2.insert(v);//把这个点扔到没法拓展的点里面
}
for(set<int>::iterator it=s1.begin();it!=s1.end();it++)
{
q.push(*it);
dist[*it]=dist[now]+1;
}
s1.swap(s2);
s2.clear();
}
}
int main()
{
int tt;
int u,v;
while(scanf("%d",&tt)!=EOF)
{
while(tt--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
scanf("%d",&start);
bfs(start);//开始
int cot=0;
for(int i=1; i<=n; i++)
{
if(i==start)
continue;cot++;
if(dist[i]==inf)
cout<<-1;
else
cout<<dist[i];
if(cot<=n-2)
cout<<" ";
}
cout<<endl;
}
}
}