【BZOJ4651】【NOI2016】网格（Tarjan，哈希）

【BZOJ4651】【NOI2016】网格（Tarjan，哈希）

题面

BZOJ

洛谷

题解

首先把题目稍微变得好说一些，给定一个网格，已经删去了若干个格子

问最少删去多少个格子使得图不连通。

这题的关键是要看出答案一定只有\(-1,0,1,2\)

证明一下一定存在答案不超过二。

在不是无解的情况下，四个角上的答案一定不会超过\(2\)

假设四个角被删去了，那么在边界上一定存在一个未被删去的格子，

一边抵着边界另外一边和一个被删去的格子相邻

（你可以认为这个角被删去了，然后这个角的限制就移动到了这个角的两侧，那么此时这个角旁边的两个点一定一端抵住了这个被删去的角的那一条边，另外一端抵着边界）

如果整个边界都被删去，那么这一行（列）就没有任何意义，可以直接考虑上面那一行（列）

所以答案一定不会超过\(2\)。

那么只需要分情况讨论即可。

我们发现图非常非常大，一点也不好搞。

所以我们按照\(x,y\)两轴分别离散，只需要离散所有被删除的点

而离散的时候额外加入左右（上下）两侧的行（列）就好了。当然，要加入两行（列）

因为如果只加入一列，会有问题，具体的反例就不给出来了。

也就是一个点加入以他为中心的，距离它曼哈顿距离为为\(4\)以内的所有点。

首先考虑答案为\(-1\)的情况

无解是什么呢？首先如果只有一个格子，显然无解。

还有一种情况，只有两个格子，并且这两个格子相邻，那么也必定无解。

如果超过了三个格子，因为这三个格子无法做到两两直接联通，所以就不存在无解的情况了。

再考虑一下\(0\)的情况，也就是啥都不用做，图就已经不连通了。

那么，考虑把所有已经被删除的格子的联通块给搞出来。

显然这个联通块周围的所有点都要在同一个集合中，直接\(bfs\)判断即可。

答案为\(1\)的时候就是在图中存在割点，并且这个割点一定和一个被删去的位置相邻。

剩下的所有情况就是\(2\)了。

我到现在还不知道为啥在UOJ上过不了Hack数据。。。。。

所有的点全部使用\(Hash\)来存储。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1000100
inline int read()
{
	RG int x=0,t=1;RG char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=-1,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return x*t;
}
int d[8][2]={1,0,0,1,-1,0,0,-1,1,1,-1,-1,-1,1,1,-1};
int n,m,C;
ll id(int i,int j){return 1ll*(i-1)*m+j;}
struct Node{int x,y;}p[MAX];
int S[MAX],len;
int vis[MAX],fr[MAX];
const int hashmod=1000007;
struct HashTable
{
	struct Node{int nt,i,j;}e[MAX<<3];
	int h[hashmod],cnt;
	void init(){memset(h,0,sizeof(h));cnt=0;}
	int Query(int i,int j)
		{
			int x=id(i,j)%hashmod;
			for(int u=h[x];u;u=e[u].nt)
				if(e[u].i==i&&e[u].j==j)return u;
			return 0;
		}
	void insert(int i,int j)
		{
			int x=id(i,j)%hashmod;
			e[++cnt]=(Node){h[x],i,j};h[x]=cnt;
		}
}H;
bool checkNoAns()
{
	if(1ll*n*m-C>2)return false;
	if(1ll*n*m-C<2)return true;
	H.init();
	for(int i=1;i<=C;++i)H.insert(p[i].x,p[i].y);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(!H.Query(i,j))
			{
				if(i!=1)if(!H.Query(i-1,j))return true;
				if(i!=n)if(!H.Query(i+1,j))return true;
				if(j!=1)if(!H.Query(i,j-1))return true;
				if(j!=m)if(!H.Query(i,j+1))return true;
			}
    return false;
}
struct Line{int v,next;}e[MAX<<3];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
bool cut[MAX];
int dfn[MAX],low[MAX],tim,gr;
vector<int> V[MAX];
void Connect(int x,int gr)
{
	vis[x]=gr;V[gr].push_back(x);
	for(int k=0;k<4;++k)
	{
		int xx=p[x].x+d[k][0],yy=p[x].y+d[k][1];
		int v=H.Query(xx,yy);
		if(v&&v<=C&&!vis[v])Connect(v,gr);
	}
}
void pre()
{
	memset(fr,0,sizeof(fr));memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(cut,0,sizeof(cut));memset(h,0,sizeof(h));
	for(int i=1;i<=gr;++i)V[i].clear();gr=0;
	tim=0;cnt=1;H.init();
	for(int i=1;i<=C;++i)H.insert(p[i].x,p[i].y);
	for(int i=1;i<=C;++i)if(!vis[i])Connect(i,++gr);
	for(int i=1;i<=C;++i)
		for(int k=0;k<8;++k)
		{
			int x=p[i].x+d[k][0],y=p[i].y+d[k][1];
			if(x<1||y<1||x>n||y>m)continue;
			int u=H.Query(x,y);if(u)continue;
			H.insert(x,y);fr[H.cnt]=true;
		}
	for(int i=H.cnt;i>C;--i)
	{
		int x=H.e[i].i,y=H.e[i].j;
		for(int k=0;k<8;++k)
		{
			int xx=x+d[k][0],yy=y+d[k][1];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(H.Query(xx,yy))continue;
			H.insert(xx,yy);
		}
	}
}
void bfs(int u,int tt)
{
	queue<int> Q;Q.push(u);vis[u]=tt;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int k=0;k<4;++k)
		{
			int x=H.e[u].i+d[k][0],y=H.e[u].j+d[k][1];
			int i=H.Query(x,y);
			if(i<=C||vis[i])continue;
			vis[i]=tt;Q.push(i);
		}
	}
}
bool check0()
{
	int tt=0;
	for(int i=C+1;i<=H.cnt;++i)if(!vis[i])bfs(i,++tt);
	for(int s=1;s<=gr;++s)
	{
		int dsu=-1;
		for(int l=V[s].size()-1;~l;--l)
		{
			int i=V[s][l];
			for(int d1=-2;d1<=2;++d1)
				for(int d2=-2;d2<=2;++d2)
				{
					int x=p[i].x+d1,y=p[i].y+d2;
					if(x<1||y<1||x>n||y>m)continue;
					int u=H.Query(x,y);if(u<=C)continue;
					if(dsu!=-1&&dsu!=vis[u])return true;
					else dsu=vis[u];
				}
		}
	}
	return false;
}
void Tarjan(int u,int ff)
{
	dfn[u]=low[u]=++tim;int son=0;
	for(int i=h[u];i;i=e[i].next)
	{
		int v=e[i].v;if(v==ff)continue;
		if(!dfn[v])
		{
			++son;Tarjan(v,u);
			if(low[v]>=dfn[u])cut[u]=true;
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(!ff&&son<2)cut[u]=false;
}
bool check1()
{
	if(n==1||m==1)return true;
	for(int i=H.cnt;i>C;--i)
	{
		int x=H.e[i].i,y=H.e[i].j;
		for(int k=0;k<4;++k)
		{
			int xx=x+d[k][0],yy=y+d[k][1];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			int u=H.Query(xx,yy);
			if(u<=C)continue;Add(i,u);
		}
	}
	for(int i=1;i<=H.cnt;++i)if(!dfn[i])Tarjan(i,0);
	for(int i=C+1;i<=H.cnt;++i)if(cut[i]&&fr[i])return true;
	return false;
}
int main()
{
	int TT=read();
	while(TT--)
	{
		n=read();m=read();C=read();
		for(int i=1;i<=C;++i)p[i].x=read(),p[i].y=read();
		if(checkNoAns()){puts("-1");continue;}
		if(!C){if(n==1||m==1)puts("1");else puts("2");continue;}
		len=0;
		for(int i=1;i<=C;++i)
		{
			S[++len]=p[i].x;S[++len]=p[i].x+1;S[++len]=p[i].x+2;
			if(p[i].x>1)S[++len]=p[i].x-1;
			if(p[i].x>2)S[++len]=p[i].x-2;
		}
		sort(&S[1],&S[len+1]);len=unique(&S[1],&S[len+1])-S-1;
		while(S[len]>n)--len;n=len;
		for(int i=1;i<=C;++i)p[i].x=lower_bound(&S[1],&S[len+1],p[i].x)-S;
		len=0;
		for(int i=1;i<=C;++i)
		{
			S[++len]=p[i].y;S[++len]=p[i].y+1;S[++len]=p[i].y+2;
			if(p[i].y>1)S[++len]=p[i].y-1;
			if(p[i].y>2)S[++len]=p[i].y-2;
		}
		sort(&S[1],&S[len+1]);len=unique(&S[1],&S[len+1])-S-1;
		while(S[len]>m)--len;m=len;
		for(int i=1;i<=C;++i)p[i].y=lower_bound(&S[1],&S[len+1],p[i].y)-S;
		pre();if(check0()){puts("0");continue;}if(check1()){puts("1");continue;}
        puts("2");
    }
}