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”
支持,希望你可以持續更新