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;
}