作者:手机用户2502869561 | 来源:互联网 | 2023-05-17 17:24
SparseGraphTimeLimit:40002000MS(JavaOthers)MemoryLimit:262144262144K(JavaOthers)T
Sparse Graph
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2612 Accepted Submission(s): 911
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
Sample Output
题意:给定一个N个顶点,M条边的无向图G,求其补图H中给定的源点S到其他N-1个点的最短距离,每条边的长度为单位长度1。
解法:利用补图求最短路,由于点比较多,所以利用链式前向星存图,建图后将已存在边标记,然后BFS收缩补图。
补图:图G的补图,通俗的来讲就是完全图K
n去除G的边集后得到的图K
n-G。在
图论里面,一个图
G的
补图(complement)或者
反面(inverse)是一个图有着跟
G相同的点,而且这些点之间有边相连
当且仅当在
G里面他们没有边相连。
的补图就是
对于BFS我们这样编写
void bfs(int start,int n)
{
set<int> s1;
set<int> s2;
set<int>::iterator it;
for(int i=1;i<=n;i++)
{
if(i!=start)
s1.insert(i);
}
dis[start]=0;
queue<int> que;
que.push(start);
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].in;
if(!s1.count(v))continue;
s1.erase(v);
s2.insert(v);
}
for(it=s1.begin();it!=s1.end();it++)
{
que.push(*it);
dis[*it]=dis[u]+1;
}
s1.swap(s2);
s2.clear();
}
}
利用两个set容器进行对已求得最短路的点、未求得的点和连接了原图边的点的区分和筛选。
例如对上诉图
先将3和2编入再依次对剩下的点进行搜索。
最后得到定点搭配其他点的最短路
全部代码如下
#include
#include
#include
#include
#include
#include
#include
#include