Sparse Graph---hdu5876（set+bfs+补图求最短路）

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5876

题意：有一个含有n个点的无向图，已知图的补图含有m条边u， v；求在原图中，起点s到其他n-1个点的最短距离，默认边的距离为1；

由于点的个数较大，不能建原图，只能从补图入手；从起点s开始，与s不直接相连的点的最短距离是1，然后再从这些点开始搜，循环即可，用队列表示，队列空了就结束了；

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

#include<set>

using namespace std;

#define met(a, b) memset(a, b, sizeof(a))

#define N 400005

#define INF 0x3f3f3f3f

typedef long long LL;

vector<vector<int> >G;

int dist[N];

void bfs(int s, int n)

{

    set<int> s1, s2;

    for(int i=; i<=n; i++)

    {

        if(i!=s) s1.insert(i);

        dist[i] = INF;

    }

    queue<int>Q;

    Q.push(s);

    dist[s] = ;

    while(Q.size())

    {

        int p = Q.front();Q.pop();

        for(int i=,len=G[p].size(); i<len; i++)

        {

            int q = G[p][i];

            if(s1.find(q) == s1.end())continue;///判断q点是否已经确定距离了；

            s1.erase(q);

            s2.insert(q);

        }

        set<int>::iterator it;

        for(it=s1.begin(); it!=s1.end(); it++)///那些到达不了的点都是可以由p点到达的；

        {

            dist[*it] = dist[p] + ;

            Q.push(*it);

        }

        s1.swap(s2);///交换s2和s1;

        s2.clear();

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n, m, start;

        scanf("%d %d", &n, &m);

        G.clear();

        G.resize(n+);

        for(int i=; i<=m; i++)

        {

            int u, v;

            scanf("%d %d", &u, &v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

        scanf("%d", &start);

        bfs(start, n);

        int f = ;

        for(int i=; i<=n; i++)

        {

            if(i == start) continue;

            f++;

            if(dist[i] == INF) dist[i] = -;

            printf("%d%c", dist[i], f == n-?'\n':' ');

        }

    }

    return ;

}