Sparse Graph
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1520 Accepted Submission(s): 537
Problem Description
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are notadjacent in G.
Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1 other vertices.
Input
There are multiple test cases. The first line of input is an integer T(1≤T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2≤N≤200000) and M(0≤M≤20000). The following M lines each contains two distinct integers u,v(1≤u,v≤N) denoting an edge. And S (1≤S≤N) is given on the last line.
Output
For each of T test cases, print a single line consisting of N−1 space separated integers, denoting shortest distances of the remaining N−1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number.
Sample Input
1
2 0
1
Sample Output
1
Source
解析：补图上的最短路。维护一个set，里面保存尚未访问的结点。BFS的扩展结点u的时候，把与u直接相连的结点排除，得到的set在补图中都与u有一条权为1的边，访问完之后把这些点从set中删除，开始下一次扩展。即在扩展结点u的时候，只扩展与u没有边相连的结点，有边相邻的结点等下一次再扩展。
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
using namespace std; const int INF = 0x3f3f3f3f;
const int MAXN = 2e5+5;
vector<int> e[MAXN];
int dis[MAXN];
int n, m, s; void bfs()
{
set<int> s1; //保存还未被访问过的结点
set<int> s2; //保存与节点u相连的结点
set<int>::iterator it;
for(int i = 1; i <= n; ++i){ //s1初始化为除结点s外的所有结点
if(i != s)
s1.insert(i);
}
queue<int> q;
q.push(s);
dis[s] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
int len = e[u].size();
for(int i = 0; i < len; ++i){
int v = e[u][i];
if(s1.find(v) == s1.end())
continue;
s1.erase(v); //把与结点u之间有边的点从s1排除
s2.insert(v); //并加入到s2
}
for(it = s1.begin(); it != s1.end(); ++it){
q.push(*it);
dis[*it] = dis[u]+1;
}
s1.swap(s2); //s1中的结点已经全部访问，s2中的结点尚未访问，二者交换
s2.clear(); //清空
}
} void solve()
{
memset(dis, INF, sizeof(dis));
for(int i = 1; i <= n; ++i)
e[i].clear();
int u, v;
while(m--){
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
scanf("%d", &s);
bfs();
for(int i = 1; i <= n; ++i){
if(i == s)
continue;
if(dis[i] >= INF)
dis[i] = -1;
printf("%d", dis[i]);
if(i != n)
printf(" ");
}
printf("\n");
} int main()
{
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
solve();
}
return 0;
}