hdu 5876 - Sparse Graph（2016大连网络赛） bfs

本文主要是介绍hdu 5876 - Sparse Graph（2016大连网络赛） bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：补图就是和原图联通状态相反的图，两个点相邻那么在补图里他们不相邻给出一个图的补图，求出s到其他点的最短距离。

用set存放还没有走到过的点，然后用bfs依次求到每个点的最短距离，到达一个点后就把这个点从set中删掉，这样可以使bfs的复杂度非常接近o（n）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 200010;
set<int> edge[MAXN], ss;
set<int>::iterator p, p1, p2;
queue<int> q;
int dist[MAXN];
int main() {int t, n, m, s, i, j;scanf("%d", &t);while(t--) {ss.clear();scanf("%d%d", &n, &m);for(i = 1; i <= n; i++) {edge[i].clear();}int a, b;for(i = 0; i < m; i++) {scanf("%d%d", &a, &b);edge[a].insert(b);edge[b].insert(a);}for(i = 1; i <= n; i++) {ss.insert(i);}memset(dist, -1, sizeof(dist));scanf("%d", &s);int xx = s;q.push(s);dist[s] = 0;ss.erase(s);
//        for(p = ss.begin(); p != ss.end(); p++)
//            cout << *p << endl;while(q.size()) {s = q.front();q.pop();
//            cout << "##  " << s << endl;for(p = ss.begin(); p != ss.end();) {
//                cout << "SS  " << edge[s].size() << endl;if(!edge[s].count(*p)) {q.push(*p);dist[*p] = dist[s] + 1;p1 = p++;ss.erase(p1);}else p++;}}int is = 0;for(i = 1; i <= n; i++) {if(i == xx) continue;if(is)printf(" ");else is = 1;printf("%d", dist[i]);}printf("\n");}return 0;
}

这篇关于hdu 5876 - Sparse Graph（2016大连网络赛） bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---