Sparse Graph

                                                                             Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)                                                                                                         Total Submission(s): 2042    Accepted Submission(s): 721 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   Recommend wange2014  

题意：在一张完全图上去掉m条边，问从一个点到其他点的最短路

解题思路：求一张补图的最短路，用set来维护还没走到的点

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; int n, m, ss; int s[200009], nt[400009], e[400009], dis[200009]; void bfs(int ss) { set<int>st, ts; for (int i = 1; i <= n; i++) { dis[i] = 0; if (i != ss) st.insert(i); } set<int>::iterator it; dis[ss] = 0; queue<int>q; q.push(ss); while (!q.empty()) { int pre = q.front(); q.pop(); for (int i = s[pre]; ~i; i = nt[i]) { int ee = e[i]; if (!st.count(ee)) continue; st.erase(ee), ts.insert(ee); } for (it = st.begin(); it != st.end(); it++) { dis[*it] = dis[pre] + 1; q.push(*it); } st.swap(ts); ts.clear(); } } int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); int cnt = 1, u, v; memset(s, -1, sizeof s); for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); if (u == v) continue; nt[cnt] = s[u], s[u] = cnt, e[cnt++] = v; nt[cnt] = s[v], s[v] = cnt, e[cnt++] = u; } scanf("%d", &ss); bfs(ss); for (int i = 1; i <= n; i++) { if (i != ss) { if (!dis[i]) printf("-1"); else printf("%d", dis[i]); if (i != n) printf(" "); } } printf("\n"); } return 0; }