HDU - 5876 Sparse Graph （关于补图中求某点到各个点最短路）
Sparse GraphTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 2830 Accepted Submission(s): 972 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 .
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来进行补图时的路的延伸。
这样的话，我们设置两个set:s1和s2, s1代表在这一轮补图中的延伸中可以被更新距离的点的集合，s2代表在到现在的所有的延伸中仍然无法更新距离值得点得集合，这样通过set得运用可以极大得避免一些不必要的查找。
#include<bits/stdc++.h>
using namespace std;
int m, n;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
struct *** {
int u, v, ne;
}ed[maxn];
int head[maxn], cnt = 0, d[maxn];
void init() {
memset(head, -1, sizeof(head));
memset(d, inf, sizeof(d));
cnt = 0;
}
void add(int u, int v) {
ed[cnt].u = u; ed[cnt].v = v;
ed[cnt].ne = head[u]; head[u] = cnt++;
}
void bfs(int st) {
queue<int>q;
set<int>s1, s2;
d[st] = 0;
q.push(st);
for (int s = 1; s <= n; s++)
if (s != st)s1.insert(s);
while (!q.empty()){
int u = q.front(); q.pop();
for (int s = head[u]; ~s; s = ed[s].ne) {
int v = ed[s].v;
if (!s1.count(v))continue;
s1.erase(v);
s2.insert(v);
}
for (set<int>::iterator now = s1.begin(); now != s1.end(); now++){
d[*now] = d[u] + 1;
q.push(*now);
}
s1.swap(s2);
s2.clear();
}
}
int main()
{
int te;
scanf("%d", &te);
while (te--) {
scanf("%d %d", &n, &m);
init();
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
int st;
scanf("%d", &st);
bfs(st); int t = 0;
for (int s = 1; s <= n; s++) {
if (d[s] == inf)d[s] = -1;
if (s == st)continue;
if (!t) {
printf("%d", d[s] );
t = 1;
}
else {
printf(" %d", d[s]);
}
}
printf("\n");
}
return 0;
}
