Sparse Graph

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

题意：

       T组样例，N个节点，M条边，源点为S。求该图补图中S到其他点的最短路长度。

依次输出路径长度。（边权均为“1”）.

思路：

       很容易想到，原图中不直接相连的点最终一定可以通过 len=1 到达，再往下就没有

什么思路了，其实我们可以通过这些补图中S可直接到达的点继续更新其他点，补图太大？

但是补图中不可到达的点是随着我们的扩展不断减少的，就是说所有点最多只进一次队列，

那边怎么办？如果我们现在有集合，里面是没有被扩展过的点（初始有N个），那对于当前

队列中取出的扩展完的点，其原图相连的所有点都应该从集合中剔除。然后集合中剩余元素

都是可以再被扩展的。。。。。所以时间复杂度只有O（N+M）。

代码实现：

#include <iostream>
#include <string.h>
#include <math.h>
#include <ctime>
#include <queue>
#include <set>
#include <stdio.h>
#include <algorithm>

#define LL long long
#define INF 0x3f3f3f3f
#define ull unsigned long long

using namespace std;

const int N = 2e5 + 100;
const int M = 4e5 + 100;
const int mod = 1e9 + 7;

int head[N], ver[M], Next[M], tot;
void add(int x, int y) {
    ver[ ++ tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

queue <int> qc;
set <int> sc, tmp_sc;
set <int>::iterator it;
int res[N];

void sol(int s, int n) {

    while (qc.size()) qc.pop();
    sc.clear();

    res[s] = 0;
    qc.push(s);
    for (int i = 1; i <= n; i ++) sc.insert(i);
    sc.erase(s);
    
    while (qc.size()) {

        int x = qc.front();
        qc.pop();
        for (int i = head[x]; i; i = Next[i]) {
            if (res[ver[i]] == -1 && ver[i] != s) {
                sc.erase(ver[i]);
                tmp_sc.insert(ver[i]);
            }
        }
		for (it = sc.begin(); it != sc.end(); ++ it) {
			res[*it] = res[x] + 1;
			qc.push(*it);	
		}
		sc.swap(tmp_sc);
		tmp_sc.clear();
    }
}

int main() {
    int t, n, m, s;
    while (scanf("%d", &t) != EOF) {
        while ( t -- ) {
            tot = 0;
            memset(res, -1, sizeof(res));
            memset(head, 0, sizeof(head));
            memset(Next, 0, sizeof(Next));

            scanf("%d %d", &n, &m);
            int x, y;
            for (int i = 1; i <= m; i ++) {
                scanf("%d %d", &x, &y);
                add (x, y);
                add (y, x);
            }
            scanf("%d", &s);
            sol(s, n);
            
            int tmp_cnt = 0;
            for (int i = 1; i <= n; i ++) {
            	if (i == s) continue;
            	printf("%d", res[i]);
                tmp_cnt ++;
                if(tmp_cnt != n-1) printf(" ");
            }
            puts("");
        }
    }
    return 0;
}

THE END;