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

 

 

Sample Output

 

1

 

 

题意：

　　

　　n 个点的无向完全图中删除 m 条边，问点 s 到其他点的最短路长度。

 

题解：

　　

　　

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              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
              
               #define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 2e5+10, M = 1e2+11, mod = 1e9+7, inf = 2e9; int T,n,m,vis[N],head[N],t,d[N],ans[N]; struct ss{ int to,next;}e[N * 2]; 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 =1;memset(head,0,sizeof(head)); for(int i = 1; i <= m; ++i) { int a,b; scanf("%d%d",&a,&b); add(a,b);add(b,a); } memset(vis,0,sizeof(vis)); memset(d,-1,sizeof(d)); int S; scanf("%d",&S); queue
               
                 q; q.push(S);vis[S] = 1; d[S] = 0; set
                
                  s; for(int i = 1; i <= n; ++i) if(i != S) s.insert(i),vis[i] = 1; 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] = 0; } } for(set
                 
                   ::iterator itt,it = s.begin();it != s.end(); ) { if(vis[*it]) { d[*it] = d[k] + 1; q.push(*it); itt = it; itt++; s.erase(it); it = itt; } else { it++; } } for(set
                  
                    ::iterator itt,it = s.begin();it != s.end(); it++) vis[*it] = 1; } int cnt = 0; for(int i = 1; i <= n; ++i) { if(i != S)ans[++cnt] = d[i]; } for(int i = 1; i < cnt; ++i) printf("%d ",ans[i]); printf("%d\n",ans[cnt]); } return 0;}