本文主要是介绍hdu5876 Sparse Graph bfs + set，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu5876 Sparse Graph bfs + set
//
// 题目链接：
// http://acm.split.hdu.edu.cn/showproblem.php?pid=5876
//
// 题目大意：
// 给定图G，求反图中固定起点s到其余各点到最短路
//
// 解题思路：
// 维护一个集合acc，在当前集合中表示可以拓展到点。
// 维护一个集合ncc，在当前集合中表示不可以拓展到点。
// bfs搜索，从当前队列中取出一点u，将图G中与u相连的
// 边从acc中删去，并添加到ncc中，并拓展acc中到点，并
// 添加到队列中，如此反复，直到队列为空。
//
// 解题感悟：
// 当时感觉这道题有点神奇，看了XJ的题解之后，发现都是
// 套路。一定要总结套路！加油 ^_^
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;const int MAXN = 2e5 + 8;
vector<int> g[MAXN];
int n;
int dist[MAXN];
void solve(int s){set<int> acc,nacc;memset(dist,0,sizeof(dist));queue<int> que;que.push(s);for (int i = 1;i <= n;i ++){if (i != s)acc.insert(i);}while(!que.empty()){int u = que.front();que.pop();for (int i = 0;i < g[u].size();i ++){int& v = g[u][i];if (!acc.count(v))continue;acc.erase(v);nacc.insert(v);}for (set<int>::iterator it = acc.begin();it != acc.end();it ++){dist[*it] = dist[u] + 1;que.push(*it);}acc.swap(nacc);nacc.clear();}int flag = 0;for (int i = 1;i <= n;i ++){if (i != s){if (flag)printf(" ");if (!dist[i])printf("-1");elseprintf("%d",dist[i]);flag = 1;}}puts("");}int main(){int t;scanf("%d",&t);while(t--){int m;scanf("%d%d",&n,&m);for (int i = 1;i <= n;i ++)g[i].clear();for (int i = 1;i <= m;i ++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}int s;scanf("%d",&s);solve(s);}return 0;
}
这篇关于hdu5876 Sparse Graph bfs + set的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
