题目描述
给你一张 $n$ 个点 $m$ 条边的随机图，边权为1。$k$ 次询问两点间最短路，不连通则输出-1。
输入
第一行包含3个正整数n,m,k(2<=n<=100000,1<=m<=300000,1<=k<=10000)，分别表示点数、边数和询问数。
接下来m行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n)，表示一条双向道路。输入数据保证不会有重边和自环。
接下来k行，每行两个正整数u_i,v_i(1<=u_i,v_i<=n,u_i!-v_i)，表示一次询问。
输入数据保证随机生成，且除了样例之外均满足n=100000,m=300000。
本题共3组数据。
输出
输出k行，每行一个整数，即最少经过的边数，若无解输出-1。
样例输入
6 5 5
1 2
2 3
1 3
1 4
4 5
1 3
4 2
3 5
5 1
4 6
样例输出
1
2
3
2
-1
题解
并查集+双向BFS最短路
使用并查集判断连通性，连通的话使用双向BFS求最短路求解。
由于数据随机，这样做可以通过（Claris的题解中有复杂度的证明，然而我弄丢了。。。）
注意双向广搜时两个方向搜索的应该染上不同的颜色。
#include <cstdio>
#define N 100010
#define M 600010
int f[N] , head[N] , to[M << 1] , next[M << 1] , cnt , vis[N] , dis[N] , q[N] , l , r;
inline void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
int solve(int x , int y , int k)
{
if(find(x) != find(y)) return -1;
int i;
l = 0 , r = -1;
vis[x] = k , dis[x] = 0 , q[++r] = x;
vis[y] = -k , dis[y] = 0 , q[++r] = y;
while(l <= r)
{
x = q[l ++ ];
for(i = head[x] ; i ; i = next[i])
{
y = to[i];
if(vis[y] == vis[x]) continue;
else if(vis[y] == -vis[x]) return dis[x] + dis[y] + 1;
else vis[y] = vis[x] , dis[y] = dis[x] + 1 , q[++r] = y;
}
}
return -1;
}
int main()
{
int n , m , k , i , x , y;
scanf("%d%d%d" , &n , &m , &k);
for(i = 1 ; i <= n ; i ++ ) f[i] = i;
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x) , f[find(x)] = find(y);
for(i = 1 ; i <= k ; i ++ ) scanf("%d%d" , &x , &y) , printf("%d
" , solve(x , y , i));
return 0;
}