Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1604    Accepted Submission(s): 565 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   Source 2016 ACM/ICPC Asia Regional Dalian Online 思路：      维护一个集合ac，在当前集合中表示可以拓展到点。      维护一个集合nac，在当前集合中表示不可以拓展到点。  bfs搜索，从当前队列中取出一点u，将图G中与u相连的边从ac中删去，并添加到nac中，并拓展ac中到点，添加到队列中，如此反复，直到队列为空。 #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<climits> #include<string> #include<queue> #include<stack> #include<set> #include<map> #include<algorithm> using namespace std; #define rep(i,j,k)for(i=j;i<k;i++) #define per(i,j,k)for(i=j;i>k;i--) #define MS(x,y)memset(x,y,sizeof(x)) typedef long long LL; const int INF=0x7ffffff; const int M=2e5+1; vector<int>g[M]; int dis[M]; int i,j,k,n,m; int s; void solve() { set<int>ac,nac; for(i=1;i<=n;i++){ if(i!=s)ac.insert(i); } queue<int>q; q.push(s); MS(dis,0); while(!q.empty()) { int u=q.front(); q.pop(); for(i=0;i<g[u].size();i++){ int &v=g[u][i]; if(!ac.count(v))continue; ac.erase(v); nac.insert(v); } for(set<int>::iterator it=ac.begin();it!=ac.end();it++){ dis[*it]=dis[u]+1; q.push(*it); } ac.swap(nac); nac.clear(); } int flag=0; for(i=1;i<=n;i++){ if(i==s)continue; if(flag)printf(" "); if(!dis[i])printf("-1"); else printf("%d",dis[i]); flag=1; } printf("\n"); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++)g[i].clear(); for(i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); g[a].push_back(b); g[b].push_back(a); } scanf("%d",&s); solve(); } return 0; }