题目：http://hdu.hustoj.com/showproblem.php?pid=5876 

 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

 

Source

 

 

 

 

题意：  给你1样例

            给你n个点和m条边

            输入m条边后

            输入起点s

 

      求原图的补图中，，起点s到各个点的最短距离并输出   

     补图 ；   一个n个点的图有n*（n-1）*0.5条边，，，除去原图上的边剩下的所有边组成补图

  

概念如图 ；

  

                                   

                        

 

 

好了题意清楚了，，其实刚开始想法很简单，，不就是补图嘛，，通过原来的图把补图还原出来，直接迪杰就ok

 

但是复杂度过高，优化是不可能的，，所以又找到了一种做法  因为只会出现3种答案吧（-1，，1，，2）

 

从起点找起，，把和起点没有联系的点用队列存起来，如图就是存4和5    更新dis[4]和dis[5]=1    

从队列中取出4和5 分别为起点  找没有联系的点3和2   更新队列和dis[3],,dis[2]=dis[4]+1;

 

好了方法已经找到了，，写出来了也，，但是还是超时 ，，想半天原来红色区域的查找复杂度也有n*（n-x)*(n-x)....显然超时

 

怎么办呢，，想到了set维护，，set能跟快速的管理和查找删除 所需要的元素  所以代码就出来了  因为对于set的维护还不熟悉只能看别人的代码，，实力太弱

 

对着网上写的代码：后面会补上自己的代码

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
            
           
          
         
        
       
      

思路并不复杂，，就是想要维护操作的时候想不到