首页 > 代码库 > hdu_5876_Sparse Graph(补图BFS)
hdu_5876_Sparse Graph(补图BFS)
题目链接：hdu_5876_Sparse Graph
附上叉姐的题解：
1009 Sparse Graph [by ftiasch]
题意：n 个点的无向完全图中删除 m 条边，问点 s 到其他点的最短路长度。
题解：
补图上的 BFS 是非常经典的问题。一般的做法是用链表（或者偷懒用 std::set）维护还没 BFS 过的点。当要扩展点 u 的时候，遍历一次还没访问过的点 v，如果 uv 没边，那么将 v 入队。否则将 v 留在未扩展点中。
很明显，后者只会发生 m 次，前者只会发生 n 次，所以复杂度是 O(n + m)O(n+m).
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 5 const int N=2e5+7,M=40010,inf=2e6+7; 6 int t,n,m,ed,v[M],nxt[M],g[N],x,y,S,d[N]; 7 8 void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;} 9 10 void fuck()11 {12 set<int>ta,tb;13 set<int>::iterator it;14 queue<int>Q;15 F(i,1,n)d[i]=inf;16 d[S]=0,Q.push(S);17 F(i,1,n)if(i!=S)ta.insert(i);18 while(!Q.empty())19 {20 int now=Q.front();Q.pop();21 for(int i=g[now];i;i=nxt[i])if(ta.find(v[i])!=ta.end())ta.erase(v[i]),tb.insert(v[i]);22 for(it=ta.begin();it!=ta.end();it++)Q.push(*it),d[*it]=d[now]+1;23 ta.swap(tb),tb.clear();24 }25 F(i,1,n)if(i!=S)printf("%d%c",d[i]==inf?-1:d[i]," \n"[i==n]);26 }27 28 int main()29 {30 scanf("%d",&t);31 while(t--)32 {33 scanf("%d%d",&n,&m),ed=0;34 F(i,1,n)g[i]=0;35 F(i,1,m)scanf("%d%d",&x,&y),adg(x,y),adg(y,x);36 scanf("%d",&S),fuck();37 }38 return 0;39 }
hdu_5876_Sparse Graph(补图BFS)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。