此文章可以使用目录功能哟↑(点击上方[+])
HDU 5876 Sparse Graph
Accept: 0 Submit: 0
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
2 0
1
Sample Output
Problem Idea
解题思路:
【题意】
给你一个n个结点,m条边的无向图G
再给你G的补图H上的一个点S
要求求出在补图H上,点S到其他n-1个结点的最短路
【类型】
BFS,最短路
【分析】
首先,我们要知道何为补图
例如下图中,图H是图G的补图,反过来说,图G是图H的补图
显而易见,图与其补图的结点数相同,而边完全不同,但若将两图合并,会发现恰好是完全图
由于题目给的图G结点数比较多,那么补图H中的结点数和边数都会很多,导致我们无法构建出补图H再采用最短路算法dijkstra或spfa等
那我们只能换个思路
由于起点S是给出的,我们可以从点S开始,进行广搜
对于点u和点v,若原图中,两点直接相连,那么补图中的这两点必定没有直接相连
但如果我们对每一点都要判断一遍有哪些点在原图中没有直接相连,这个复杂度还是很高的
所以我们可以采用std::set维护还没BFS过的点
当要扩展点u的时候,遍历一次还没访问过的点v
如果u和v之间没边,那么将v入队;否则将v留在未扩展点中
【时间复杂度&&优化】
O(m+n)
题目链接→HDU 5876 Sparse Graph
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 200005;
const int M = 20005;
const int inf = 1000000007;
const int mod = 7;
struct edge
{int v,to;
}e[2*M];
struct node
{int u,d;node(){}node(int _u,int _d):u(_u),d(_d){}
};
int n,p,h[N],d[N];
void add_edge(int u,int v)
{e[p].v=v;e[p].to=h[u];h[u]=p++;
}
void bfs(int s)
{int i;node u;queue<node> q;set<int> a,b;set<int>::iterator it;q.push(node(s,0));for(i=1;i<=n;i++)if(i!=s)a.insert(i);while(!q.empty()){u=q.front();q.pop();for(i=h[u.u];i+1;i=e[i].to){it=a.find(e[i].v);if(it!=a.end()){a.erase(it);b.insert(e[i].v);}}for(it=a.begin();it!=a.end();it++){d[*it]=u.d+1;q.push(node(*it,d[*it]));}a.swap(b);b.clear();}
}
int main()
{int t,m,i,k,u,v,s;scanf("%d",&t);while(t--){p=0;memset(d,-1,sizeof(d));memset(h,-1,sizeof(h));scanf("%d%d",&n,&m);for(i=0;i<m;i++){scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);}scanf("%d",&s);bfs(s);for(k=0,i=1;i<=n;i++)if(i!=s){printf("%d",d[i]);k++;if(k<n-1)printf(" ");}puts("");}return 0;
}