链接：https://www.luogu.com.cn/problem/P1173
题目描述：有一个\(n\times m\)的棋盘，有\(c\)只蛐蛐，求再放置多少只蛐蛐可以使图中其他部分被分成两部分。
题解：由于可以在这个图剩余部分的角落放，答案就只有\(-1,0,1,2\)。
考虑这个题目本身就是一个关键点的模型，这样我们可以加入八连通格，然后跑连通与割点，就可以算出答案，对于本身无交的分开考虑，但又有这种情况：
红色的叉会误判为割点，于是我们考虑将上面三个格子也加入关键点：
橙色的叉又会被误判为个点，于是我们考虑将角落的格子也加入关键点：
但又有这种情况：
如图所示，红色的叉会误判割点，但此时我们可以连上那几条蓝色的边，这样就避免了这种情况。
当然\(n=1,m=1\)的情况要特判，\(map\)太慢了，可以换成\(hash\)表，这样就能过了。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define RG register
using namespace std;
struct node
{
int x,y;
bool operator < (const node &a)const
{
if (x!=a.x)
return x<a.x;
return y<a.y;
}
bool operator == (const node &a)const
{
return (x==a.x)&&(y==a.y);
}
};
struct ed
{
int v,nxt;
};
ed edge[20000001];
int len,head[2500001];
long long T,n,m,c,length;
node P[2500001],s[100001],D[2500001];
node tmp;
inline node make_node(RG int x,RG int y)
{
tmp.x=x;
tmp.y=y;
return tmp;
}
inline int read()
{
char c=0;
RG int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
inline void add(RG int x,RG int y)
{
if (x==0||y==0)
return;
edge[++len].v=y;
edge[len].nxt=head[x];
head[x]=len;
edge[++len].v=x;
edge[len].nxt=head[y];
head[y]=len;
return;
}
int rt[2500001],dfn[2500001],low[2500001],leng,L;
inline int find(RG int x)
{
if (rt[x]==x)
return x;
return rt[x]=find(rt[x]);
}
inline void unionn(RG int x,RG int y)
{
rt[x]=y;
return;
}
vector<int>S[2500001];
bool used[2500001],cut[2500001];
void dfs(RG int x)
{
used[x]=1;
for (RG int i=head[x];i>0;i=edge[i].nxt)
if (!used[edge[i].v])
dfs(edge[i].v);
return;
}
inline void tarjan(RG int x,RG int rt)
{
dfn[x]=low[x]=++leng;
RG int cnt=0;
for (RG int i=head[x];i>0;i=edge[i].nxt)
{
if (!dfn[edge[i].v])
{
tarjan(edge[i].v,rt);
if (low[edge[i].v]>=dfn[x])
{
cnt++;
if (cnt==2||x!=rt)
cut[x]=1;
}
low[x]=min(low[x],low[edge[i].v]);
}
else
low[x]=min(low[x],dfn[edge[i].v]);
}
return;
}
long long mod=845997;
vector<node>has[1000001];
vector<int>has2[1000001];
void Insert(node a,int b)
{
has[(a.x*231ll+a.y*457ll)%mod].push_back(a);
has2[(a.x*231ll+a.y*457ll)%mod].push_back(b);
return;
}
int Find(node a)
{
int tmp=(a.x*231ll+a.y*457ll)%mod;
for (int i=0;i<has[tmp].size();++i)
if (has[tmp][i]==a)
return has2[tmp][i];
return -1;
}
inline void work()
{
RG int t=0;
n=read(),m=read(),c=read();
len=length=leng=L=0;
for (RG int i=0;i<=1000000;++i)
has[i].clear(),has2[i].clear();
for (RG int i=1;i<=24*c;++i)
rt[i]=head[i]=used[i]=cut[i]=dfn[i]=low[i]=0,S[i].clear(),P[i].x=P[i].y=s[i].x=s[i].y=0;
for (RG int i=1;i<=c;++i)
{
s[i].x=read(),s[i].y=read();
Insert(s[i],0);
}
if (n*m-c<=1)
{
puts("-1");
return;
}
if (n*m-c==2)
{
for (RG int i=1;i<=n;++i)
for (RG int j=1;j<=m;++j)
if (Find(make_node(i,j))==-1)
{
if (i+1<=n&&Find(make_node(i+1,j))==-1)
{
puts("-1");
return;
}
if (j+1<=m&&Find(make_node(i,j+1))==-1)
{
puts("-1");
return;
}
}
}
if (n==1||m==1)
{
RG int tt=0;
t=0;
sort(s+1,s+c+1);
if (n==1)
s[0].x=s[c+1].x=1,s[0].y=0,s[c+1].y=m+1;
else
s[0].y=s[c+1].y=1,s[0].x=0,s[c+1].x=n+1;
for (int i=1;i<=c+1;++i)
{
if (s[i].x+s[i].y-s[i-1].x-s[i-1].y>=4)
t=1;
if (s[i].x+s[i].y-s[i-1].x-s[i-1].y>=2)
tt++;
}
if (t==1&&tt==1)
{
puts("1");
return;
}
}
for (RG int i=1;i<=c;++i)
for (RG int j=max(1,s[i].x-2);j<=min(n,s[i].x+2ll);++j)
for (RG int k=max(1,s[i].y-2);k<=min(m,s[i].y+2ll);++k)
{
if (Find(make_node(j,k))==-1)
{
P[++length]=make_node(j,k);
S[length].push_back(i);
Insert(make_node(j,k),length);
}
else if (Find(make_node(j,k))!=0)
S[Find(make_node(j,k))].push_back(i);
}
for (RG int i=1;i<=length+c;++i)
rt[i]=i;
for (RG int i=1;i<=c;++i)
for (RG int k=0;k<=1;++k)
if (Find(make_node(s[i].x+4,s[i].y+k*8-4))==0)
{
if (Find(make_node(s[i].x+1,s[i].y+k*6-3))!=0)
add(Find(make_node(s[i].x+2,s[i].y+k*6-3)),Find(make_node(s[i].x+1,s[i].y+k*4-2)));
if (Find(make_node(s[i].x+3,s[i].y+k*2-1))!=0)
add(Find(make_node(s[i].x+2,s[i].y+k*2-1)),Find(make_node(s[i].x+3,s[i].y+k*4-2)));
}
for (RG int i=1;i<=length;++i)
for (RG int j=0;j<S[i].size();++j)
if (find(i)!=find(S[i][j]+length))
unionn(find(S[i][j]+length),find(i));
for (RG int i=1;i<=length;++i)
for (RG int j=0;j<=1;++j)
if (Find(make_node(P[i].x+j,P[i].y+1-j))!=-1)
{
t=Find(make_node(P[i].x+j,P[i].y+1-j));
if (find(t)!=find(i))
continue;
if (t==0)
continue;
add(i,t);
}
for (RG int i=1;i<=length;++i)
if (find(i)==i)
dfs(i);
for (RG int i=1;i<=length;++i)
if (used[i]==0)
{
puts("0");
return;
}
for (RG int i=1;i<=length;++i)
if (!dfn[i])
tarjan(i,i);
for (RG int i=1;i<=length;++i)
if (cut[i])
{
puts("1");
return;
}
puts("2");
return;
}
int main()
{
T=read();
while (T--)
work();
return 0;
}