首页 > 代码库 > hdu 5876 Sparse Graph 无权图bfs求最短路

hdu 5876 Sparse Graph 无权图bfs求最短路

2024-08-14 21:51:03   210人阅读

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)


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
12 01
 

 

Sample Output
1
 

 

Source
2016 ACM/ICPC Asia Regional Dalian Online 
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))const int N=1e5+10,M=4e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;vector<int>v[N<<1];queue<int>q;set<int>s;int flag[N<<1];int ans[N<<1];void init(int n){    s.clear();    for(int i=1;i<=n;i++)        v[i].clear(),flag[i]=1,ans[i]=0;    while(!q.empty())q.pop();}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n,m;        scanf("%d%d",&n,&m);        init(n);        for(int i=0;i<m;i++)        {            int u,w;            scanf("%d%d",&u,&w);            v[u].push_back(w);            v[w].push_back(u);        }        int st;        scanf("%d",&st);        q.push(st);        for(int i=1;i<=n;i++)if(i!=st)s.insert(i);        flag[st]=0,ans[st]=0;        while(!q.empty())        {            int u=q.front();            q.pop();            for(int i=0;i<v[u].size();i++)                flag[v[u][i]]=0;            for(set<int>::iterator itt,it=s.begin();it!=s.end();)            {                if(flag[*it])                {                    q.push(*it);                    ans[*it]=ans[u]+1;                    itt=it;                    it++;                    s.erase(itt);                }                else                    it++;            }            for(set<int>::iterator it=s.begin();it!=s.end();it++)flag[*it]=1;        }        int flag=0;        for(int i=1;i<=n;i++)        {            if(i==st)            continue;            printf("%d%c",ans[i],(flag++>=(n-2)?‘\n‘:‘ ‘));        }    }    return 0;}

 

hdu 5876 Sparse Graph 无权图bfs求最短路


联系
我们