题意:
给一个含n个点，m条边的无向图，已知补图就是原图边的补集，问一个点s在补图中与其他所有点的最短距离分别是多少，如果点s与某点不相连则输出-1。
下方法都是根据大部分博客的想法所做，即BFS + set去重复。
在BFS过程的队列中，第一层必然是原图中与点s不直接相连的点（即补图中直接相连的点），而后续加入队列的点必然是原图中与点s相连的点。
由于原图中边的数量基本小于点的数量，所以补图为密集图，边数多，点数量较少，用set存BFS下一层的点则可以大大减少BFS次数。
#include <iostream> #include <algorithm> #include <string> #include <set> #include <queue> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; typedef pair<int, int> Point; const int MAXN = 2e5 + 5; const int MAXM = 2e4 + 2; set<int> lib[MAXN]; set<int> :: iterator it; set<int> con; set<int> discon; int answer[MAXN]; queue<int> que; void bfs(const int n, const int s) { while(!que.empty()) que.pop(); for(it = con.begin(); it != con.end(); ++it) que.push ( *it ); int now; while(!que.empty()) { now = que.front(); que.pop(); for( it = discon.begin(); it != discon.end(); ++it) { if( lib[now].count( *it ) == 0) { answer[ *it ] = answer[ now ] + 1; discon.erase( *it ); que.push( *it ); } } } } void solve() { int T, n, m, s, a, b; scanf("%d", &T); while(T--) { bool flag = false; con.clear(); discon.clear(); scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { lib[i].clear(); answer[i] = -1; } for(int i = 0; i < m; ++i) { scanf("%d%d", &a, &b); lib[a].insert(b); lib[b].insert(a); } scanf("%d", &s); for(int i = 1; i<= n; ++i) { if( s != i && lib[i].count( s ) == 0) { answer[i] = 1; con.insert( i ); } } for(int i = 1; i <= n; ++i) { if( lib[i].size() == 0) { flag = true; break; } } for(it = lib[s].begin(); it != lib[s].end(); ++it) { discon.insert( *it ); } if(flag) { for(it = con.begin(); it != con.end(); ++it) answer[ *it ] = 1; for(it = discon.begin(); it != discon.end(); ++it) answer[ *it ] = 2; } else { bfs(n, s); } flag = false; for(int i = 1; i <= n; ++i) { if(i != s) { if(flag) putchar(' '); else flag = true; printf("%d", answer[i]); } } putchar('\n'); } } int main() { solve(); return 0; }
