本文共 2342 字，大约阅读时间需要 7 分钟。
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 not adjacent 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 1Sample Output
1题意：给出一个原图，求补图的最短路
分析：比赛的时候一心想先建完全图，再忽略原图中的边来求最短路，换了各种模板，结果不是时间超就是内存超，结论是不能建完全图来算这道题（二十万个点的完全图。。。），结果比赛完了也没想到方法，我真的是很菜。。。 网上找到的题解是存原图，暴力枚举所有点，如果与起点的边不在原图中，那么距离就是起点的距离+1，然后用BFS再把这些点设为起点，再枚举剩下的没算出距离的点。。。 原博主写得有点抽象，我照着自己的理解写了份代码#include#include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f#define MAXN 200005#define Mod 10001using namespace std;int n,m,dis[MAXN];set all,mp[MAXN],tmp;queue q;int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { all.insert(i); //先把所有顶点加入 mp[i].clear(); } memset(dis,-1,sizeof(dis)); int u,v,s; while(m--) { scanf("%d%d",&u,&v); mp[u].insert(v); mp[v].insert(u); } scanf("%d",&s); q.push(s); dis[s]=0; all.erase(s); while(!q.empty()) { tmp.clear(); u=q.front(); q.pop(); set ::iterator v=all.begin(); for(;v!=all.end();v++) //遍历所有顶点 { if(mp[u].find(*v)==mp[u].end()) //不在原图中的边说明补图中可以到达 { dis[*v]=dis[u]+1; tmp.insert(*v); //这些点下次就不用考虑 q.push(*v); //以当前距离为起点（第一次距离为1），寻找距离+1的点 } } for(v=tmp.begin();v!=tmp.end();v++) //在所有顶点中删除已经算过的点 all.erase(*v); } bool flag=false; for(int i=1;i<=n;++i) { if(i!=s) { if(flag) printf(" %d",dis[i]); else printf("%d",dis[i]); flag=true; } } printf("\n"); } return 0;}
转载地址：http://xpcvb.baihongyu.com/