P4334 [COI2007] Policija

题意

一个无重边的无向图，每次询问删掉一条边或删掉一个点后两个点是否联通。

思路

连通性问题，我们可以考虑使用广义圆方树解决。

对于删掉一个点的情况：

我们先跑 tarjan 建出圆方树。如何判断两点在删去一个点后在树上的连通性？当且仅当被删去的点在两点间的路径上。根据圆方树的性质，如果被删点在一个点双连通分量中，它是符合上面的判断条件的。

所以，我们只需要建出圆方树，判断这个点是否在询问的两点间的路径上就行了。

对于删掉一条边的情况：

考虑我们建出来的广义圆方树是一种怎样的形态。它一定是圆方点交错的形式。换句话说，一条边若不在点双连通分量内，它就会变成一个方点，并连接其原来的两个点。

换句话说，我们把一条边转化成了一个点。于是我们就可以像上面处理点一样处理了。

实现

判断一个点是否在两点路径上，我们可以用树剖实现。具体来讲，在跳LCA的过程中判断被删点是否在起终点之间，我们用链首和深度判断即可。

由于题目查询边的给出方式约束，我们可以用 map 实现查询边是否在点双内。代码中，minmax 函数为 C++11 语法，其返回值为一个排好序后的 pair 。

整体时间复杂度为 \(O(n+q(\log n+\log m))\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cmath>

#include<map>

using namespace std;

inline int read(){

	int w=0,x=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

	return w?-x:x;

}

namespace star

{

	const int maxn=2e5+10,maxm=5e5+10;

	typedef pair<int,int> pii;

	int n,m;

	struct gragh{

		int ecnt,head[maxn],to[maxm<<1],nxt[maxm<<1];

		inline void addedge(int a,int b){

			to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;

			to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;

		}

	}G1,G2;

	int tot,cnt,st[maxn],dfn[maxn],low[maxn];

	map<pii,int> mp;

	void tarjan(int x,int f){

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

		st[++st[0]]=x;

		for(int i=G1.head[x];i;i=G1.nxt[i]){

			int u=G1.to[i];

			if(u==f)continue;

			if(!dfn[u]){

				tarjan(u,x);

				low[x]=min(low[x],low[u]);

				if(low[u]>=dfn[x]){

					cnt++;

					if(low[u]>dfn[x]) mp.insert(make_pair(minmax(u,x),cnt));

					G2.addedge(cnt,x);

					int now=-1;

					while(now^u)

						now=st[st[0]--],G2.addedge(now,cnt);

				}

			}else low[x]=min(low[x],dfn[u]);

		}

	}

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

	void dfs1(int x,int f){

		fa[x]=f,dep[x]=dep[f]+1;siz[x]=1;

		for(int i=G2.head[x];i;i=G2.nxt[i]){

			int u=G2.to[i];

			if(u==f)continue;

			dfs1(u,x);

			siz[x]+=siz[u];

			if(siz[u]>siz[son[x]])son[x]=u;

		}

	}

	void dfs2(int x,int topf){

		top[x]=topf;

		if(!son[x]) return;

		dfs2(son[x],topf);

		for(int i=G2.head[x];i;i=G2.nxt[i]){

			int u=G2.to[i];

			if(u==fa[x] or u==son[x]) continue;

			dfs2(u,u);

		}

	}

	inline bool LCA(int x,int y,int z){

		while(top[x]!=top[y]){

			if(dep[top[x]]<dep[top[y]])swap(x,y);

			if(top[x]==top[z] and dep[z]<=dep[x]) return 1;

			x=fa[top[x]];

		}

		if(dep[x]<dep[y])swap(x,y);

		if(top[x]==top[z] and dep[z]>=dep[y] and dep[z]<=dep[x]) return 1;

		return 0;

	}

	inline void work(){

		n=cnt=read(),m=read();

		for(int i=1;i<=m;i++) G1.addedge(read(),read());

		tarjan(1,0);

		dfs1(1,0);

		dfs2(1,1);

		int Q=read();

		while(Q--)

			if(read()==1){

				int x=read(),y=read();

				map<pii,int>::iterator it=mp.find(minmax(read(),read()));

				if(it==mp.end()) puts("yes");

				else puts(LCA(x,y,(*it).second)?"no":"yes");

			}else{

				int x=read(),y=read(),z=read();

				puts(LCA(x,y,z)?"no":"yes");

			}

	}

}

signed main(){

	star::work();

	return 0;

}

巴特西

P4334 [COI2007] Policija

P4334 [COI2007] Policija

题意

思路

实现

代码

最新文章

热门文章