1. 首页
2. 图论
3. 本页

HDU 5876 Sparse Graph (补图的最短路)

题目链接：点我~~

题意：给出一个无向图，要求求该图的补图，然后问指定点S到其它n-1个顶点的最短距离。

思路：

补图上的 BFS 是非常经典的问题。一般的做法是用链表（或者偷懒用 std::set）维护还没 BFS 过的点。当要扩展点 u 的时候，遍历一次还没访问过的点 v，如果 uv 没边，那么将 v 入队。否则将 v 留在未扩展点中。

很明显，后者只会发生 m 次，前者只会发生 n 次，所以复杂度是 O(n + m).

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 200100;

int n,m;
int dis[MAXN];

struct Edge
{
    int to,next;
} edge[MAXN*2];
int tot;
int head[MAXN],vis[MAXN];

void add_edge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void bfs(int s)
{
    queue<int> q;
    set<int> s1,s2;
    dis[s]=0;
    q.push(s);
    for(int i = 1; i <= n; i++)
    {
        if(i==s)
            continue;
        s1.insert(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!s1.count(v))
                continue;
            s1.erase(v);
            s2.insert(v);
        }
        for(auto it = s1.begin(); it != s1.end(); it++)
        {
            q.push(*it);
            dis[*it] = dis[u] + 1;
        }
        s1.swap(s2);
        s2.clear();
    }
}


int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d%d",&n,&m);
            tot = 1;
            memset(head,-1,sizeof(head));
            memset(dis,INF,sizeof(dis));
            int x,y,s;
            for(int i = 0; i < m; i++)
            {
                scanf("%d%d",&x,&y);
                add_edge(x,y);
                add_edge(y,x);
            }
            scanf("%d",&s);
            bfs(s);
            bool flg=1;
            for(int i=1; i<=n; ++i)
            {
                if(i==s)
                    continue;
                if(!flg)
                {
                    printf(" ");
                }
                flg=0;
                if(dis[i]==INF)
                {
                    printf("-1");
                }
                else
                {
                    printf("%d",dis[i]);
                }
            }
            puts("");
        }

    }
    return 0;
}