HDU 5876 Sparse Graph

Sparse Graph Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1489 Accepted Submission(s): 521 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

水题啊…..英语不好 网赛的时候瞄了几眼 就没看下去了….. 用链表记录还没到过的点 到一个删一个 set<pair<int,int> >记录原图中有的边(不可通过的边) BFS跑一遍 其实最多才进行n+m次松弛操作

#include<iostream> #include<stdlib.h> #include<stdio.h> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> #include<time.h> #include<math.h> #include<list> #include<cstring> #include<fstream> #include<bitset> //#include<memory.h> using namespace std; #define ll long long #define ull unsigned long long #define pii pair<int,int> #define INF 1000000007 const int N=200000+5; set<pii>exist; int dis[N]; list<int>ls; void bfs(int s,int n){ fill(dis,dis+n+1,-1); ls.clear(); for(int i=1;i<=n;++i) if(i!=s) ls.push_back(i); deque<int>de; de.push_back(s); dis[s]=0; while(!de.empty()){ int fr=de.front(); de.pop_front(); if(ls.empty()) break; for(list<int>::iterator it=ls.begin();it!=ls.end();){ if(exist.find({*it,fr})!=exist.end()) ++it; else{ de.push_back(*it); dis[*it]=dis[fr]+1; list<int>::iterator tmp=it; ++it; ls.erase(tmp); } } } } int main() { //freopen("/home/lu/文档/r.txt","r",stdin); //freopen("/home/lu/文档/w.txt","w",stdout); int t,n,m,u,v,s; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); exist.clear(); while(m--){ scanf("%d%d",&u,&v); exist.insert({u,v}); exist.insert({v,u}); } scanf("%d",&s); bfs(s,n); bool flag=false; for(int i=1;i<=n;++i){ if(i!=s){ if(flag==false) flag=true; else printf(" "); printf("%d",dis[i]); } } putchar('\n'); } return 0; }