Sparse Graph
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
2 0
1
Sample Output
1
题意：
n 个点的无向完全图中删除 m 条边，问点 s 到其他点的最短路长度。
题解：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
using namespace std; #pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair typedef long long LL;
const long long INF = 1e18;
const double Pi = acos(-1.0);
const int N = 2e5+, M = 1e2+, mod = 1e9+, inf = 2e9; int T,n,m,vis[N],head[N],t,d[N],ans[N];
struct ss{int to,next;}e[N * ];
void add(int u,int v) {e[t].to=v;e[t].next=head[u];head[u]=t++;} int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
t =;memset(head,,sizeof(head));
for(int i = ; i <= m; ++i) {
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
memset(vis,,sizeof(vis));
memset(d,-,sizeof(d));
int S;
scanf("%d",&S);
queue<int > q;
q.push(S);vis[S] = ;
d[S] = ;
set<int > s;
for(int i = ; i <= n; ++i) if(i != S) s.insert(i),vis[i] = ;
while(!q.empty()) {
int k = q.front();
q.pop();
for(int i = head[k]; i; i =e[i].next) {
int to = e[i].to;
if(s.count(to)) {
vis[to] = ;
}
}
for(set<int > ::iterator itt,it = s.begin();it != s.end(); ) {
if(vis[*it])
{
d[*it] = d[k] + ;
q.push(*it);
itt = it;
itt++;
s.erase(it);
it = itt;
} else {
it++;
}
}
for(set<int > ::iterator itt,it = s.begin();it != s.end(); it++) vis[*it] = ;
}
int cnt = ;
for(int i = ; i <= n; ++i) {
if(i != S)ans[++cnt] = d[i];
}
for(int i = ; i < cnt; ++i) printf("%d ",ans[i]);
printf("%d\n",ans[cnt]);
}
return ;
}