Hyperspace Highways

wjh15101051's space

卧薪尝胆，厚积薄发。

Hyperspace Highways

Date: Sat Oct 27 13:59:56 CST 2018

In Category: NoCategory

Description：

给一个图，保证每个点双都是一个团，多次询问两点间最短路。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 3\times 10^5$

Solution：

先把点双缩点，建一棵圆方树，把边权设成 $0.5$ ，这时树上两个点的距离就是原图中两个点的距离，树剖即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 200010

#define MAXM 500010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

struct edges

{

	int u,v;

}es[MAXN];

int en = 0;

int cur;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] >= dfn[k])

			{

				++cur;

				int t;

				do

				{

					t = s.top();s.pop();

					es[++en] = (edges){t,cur};

				}while(t != e[i].to);

				es[++en] = (edges){k,cur};

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	return;

}

int top[MAXN],dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	cur = n;

	for(int i = 1;i <= n;++i)

	{

		if(dfn[i] == 0)tarjan(i);

	}

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	for(int i = 1;i <= en;++i)

	{

		add(es[i].u,es[i].v);

	}

	dfs1(1,1);dfs2(1,1);

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		printf("%d\n",(dep[a] + dep[b] - 2 * dep[LCA(a,b)]) / 2);

	}

	return 0;

}

In tag: 图论-连通性-圆方树图论-连通性-tarjan 图论-连通性-点双连通分量

wjh15101051