首页 > 代码库 > HDOJ5876(补图的最短路)

HDOJ5876(补图的最短路)

2024-08-13 10:34:48   221人阅读

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1563    Accepted Submission(s): 549


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 notadjacent 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
 
思路：边的长度均为1，用bfs。遍历补图中与u相连接的结点v，并将其在全部结点的集合中删除。删除结点用set较快。
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>#include <set>using namespace std;const int MAXN=200005;vector<int> arc[MAXN];set<int> node;int n,m,s;int vis[MAXN],d[MAXN];void bfs(int src){    memset(vis,0,sizeof(vis));    memset(d,-1,sizeof(d));    queue<int> que;    que.push(src);    vis[src]=1;    d[src]=0;    node.erase(src);    while(!que.empty())    {        int u=que.front();que.pop();        vector<int> vec;        for(set<int>::iterator it=node.begin();it!=node.end();it++)        {            int to=*it;            if(!vis[to]&&!binary_search(arc[u].begin(),arc[u].end(),to))            {                d[to]=d[u]+1;                vis[to]=1;                que.push(to);                            vec.push_back(to);            }        }        for(int i=0;i<vec.size();i++)        {            node.erase(vec[i]);        }    }    }int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        node.clear();        for(int i=1;i<=n;i++)        {            node.insert(i);            arc[i].clear();        }        for(int i=0;i<m;i++)        {            int u,v;            scanf("%d%d",&u,&v);            arc[u].push_back(v);            arc[v].push_back(u);        }        for(int i=1;i<=n;i++)        {            sort(arc[i].begin(),arc[i].end());        }        scanf("%d",&s);        bfs(s);        bool tag=false;        for(int i=1;i<=n;i++)        {            if(i==s)    continue;            if(tag)    printf(" ");            tag=true;            printf("%d",d[i]);            }        printf("\n");    }    return 0;}

 

HDOJ5876(补图的最短路)


联系
我们