大连网络赛的倒数第二题，比赛时想的太多了，没有A掉，挺可惜的！以下是题目

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1495    Accepted Submission(s): 525 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  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 1   Sample Output 1 题目的意思就是给你一个图与及一个起点，再根据给出的图找出这个图完全图的补图，最后求出补图上除起点外每个点到起点的距离（以为边没有权值，距离为起点到该点的最小边数）。 解题思路： 首先储存一下刚开始时图的边，而这些边在补图上不会存在，如果没有储存的边都是补图上的边， 这样就可以做出了补图。然后在补图上找出距离从1到n-1的点（因为一个图上两点之间的最长距离为n-1），找不到就无法到达起点，距离用一个数组储存。 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int big = 2e5 + 7; const int INF = 0x7f7f7f7f; vector<int>z[big]; int dis[big], n, m, k, record[big], num1, num2; int fuck[big], sum, mid[big], amout; bool vis[big]; void initialization() { for(int i = 1; i <= n; i ++) { dis[i] = -1; z[i].clear(); } } bool judge(int key) { int temp = 0; for(int i = 0, j = z[key].size(); i < j; i ++) if(vis[z[key][i]]) temp ++; return temp < num2; } void bfs() { bool flag; for(int i = 1, d; i < n; i ++) { flag = true; sum = 0; for(int j = 1; j <= num1; j ++) { d = record[j]; if(!judge(d)) continue; flag = false; fuck[++ sum] = d; record[j] = 0; } if(flag) return; /// 此处是优化，因为当距离为i时，没有点能到达，距离大于i的点不存在！ for(int j = 1; j <= sum; j ++) { d = fuck[j]; vis[d] = true; dis[d] = i; } amout = 0; for(int j = 1; j <= num1; j ++) { if(!record[j]) continue; mid[++ amout] = record[j]; } for(int j = 1; j <= amout; j ++) record[j] = mid[j]; num1 -= sum; num2 += sum; } } int main() { int t, u, v; scanf("%d", &t); while(t --) { scanf("%d %d", &n, &m); initialization(); for(int i = 1; i <= m; i ++) { scanf("%d %d", &u, &v); z[u].push_back(v); z[v].push_back(u); } scanf("%d", &k); memset( vis, false, sizeof( vis)); num1 = 0; for(int i = 1; i <= n; i ++) { if(i == k) continue; record[++ num1] = i; } num2 = n - num1; dis[k] = 0; vis[k] = true; bfs(); for(int i = 1, s = 0; i <= n; i ++) { if(!dis[i]) continue; if(s ++) printf(" "); printf("%d", dis[i]); } printf("\n"); } return 0; }