HDU 5876 大连网络赛 Sparse Graph
Sparse Graph
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 928 Accepted Submission(s): 312
Problem Description
In graph theory, the of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are adjacent in . Now you are given an undirected graph of nodes and bidirectional edges of length. Consider the complement of , i.e., . For a given vertex on , you are required to compute the shortest distances from to all other vertices.
Input
There are multiple test cases. The first line of input is an integer denoting the number of test cases. For each test case, the first line contains two integers and . The following lines each contains two distinct integers denoting an edge. And is given on the last line.
Output
For each of test cases, print a single line consisting of space separated integers, denoting shortest distances of the remaining vertices from (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
补图上的BFS因为补图是一个完全图，然后去掉最多两万条边，有可以想象，从起点到任何一点的最短距离肯定很短，我可以从起点开始扫把所有没有和起点有边的（原图中）入队列，这是第一层距离为1的，然后以这些点继续扩展，因为最短距离很短，最多扩展10次就把所有点都扫过了，已经扩展过的点在bfs过程中就不要扫了，所以可以set或者vector把扩展过的点删除#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#include <vector>
#include <queue>
using namespace std;
const int maxn=2*1e5;
int n,m,k;
int d[maxn+5];
set<int> a[maxn+5];
set<int> s;
queue<int> q;
int de[maxn+5];
void BFS(int x)
{
q.push(x);
memset(d,-1,sizeof(d));
d[x]=0;
while(!q.empty())
{
int term=q.front();
q.pop();
int cnt=0;
for(set<int>::iterator it=s.begin();it!=s.end();it++)
{
bool tag=true;
int i=*it;
if(a[i].find(term)==a[i].end())
{
d[i]=d[term]+1;
q.push(i);
de[cnt++]=i;
}
}
for(int i=0;i<cnt;i++)
s.erase(de[i]);
}
}
int main()
{
int t;
int x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
s.clear();
for(int i=1;i<=n;i++)
s.insert(i),a[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].insert(y);
a[y].insert(x);
}
scanf("%d",&k);
s.erase(k);
BFS(k);
for(int i=1;i<=n;i++)
{
if(i==k)
continue;
printf("%d",d[i]);
if(i!=n)
printf(" ");
}
printf("\n");
}
return 0;
}