REPORT HDU5876-Sparse Graph

# REPORT HDU5876-Sparse Graph

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 403 Accepted Submission(s): 133

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 //======================================================= 比赛的时候以为是最短路，就开始求补然后突然发现邻接表邻接矩阵好像都没法存补图…… 我居然没从另一个侧面去想一下…… MDZZ…… 比完赛看完题解才知道原来BFS就好了…… //======================================================= 感谢dalao的题解
//=======================================================

```#include <iostream>
#include <set>
#include <queue>
#define MAXN 200020
#define MAXM 50005
#define INF  0x3F3F3F3F
using namespace std;

int n, m, edges, g[MAXN], nxt[MAXM], v[MAXM], S, d[MAXN];

void BFS()
{
set<int> a, b;
set<int>::iterator it;
queue<int> Q;
for (int i = 1; i <= n; i++) d[i] = INF;
d[S] = 0;
Q.push(S);
for (int i = 1; i <= n; i++)
if (i != S) a.insert(i);
while (!Q.empty())
{
int now;
now = Q.front();
Q.pop();
for (int i = g[now]; i; i = nxt[i])
if (a.find(v[i]) != a.end())
{
a.erase(v[i]);
b.insert(v[i]);
}
for (it = a.begin(); it != a.end(); it++)
{
Q.push(*it);
d[*it] = d[now] + 1;
}
a.swap(b);
b.clear();
}
for (int i = 1; i < n; i++)
{
if (i != S) cout << (d[i] == INF ? -1 : d[i]) << ' ';
}
cout << d[n];
cout << endl;
}

int main()
{
int T; cin >> T;
while (T--)
{
edges = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) g[i] = 0;
for (int i = 1; i <= m; i++)
{
int U, V;
cin >> U >> V;
v[++edges] = V, nxt[edges] = g[U], g[U] = edges;
v[++edges] = U, nxt[edges] = g[V], g[V] = edges;
}
cin >> S;
BFS();
}
return 0;
}
```

## One Reply to “REPORT HDU5876-Sparse Graph”

1. 搞笑影片说道：

支持，希望你可以持續更新