题解
之前用的mapTLE了，今天用了个hash把题卡了过去，AC数++
我们只要保留一个点为中心周围5 * 5个格子就可以
如果一个点周围5*5个格子有两个不连通，那么显然输出0
如果一个出现了一个割点，那么看看这个割点在不在离中心点的第一层，如果在的话就是1，没有合法割点的话就是2
然后就是特判了……特判真的挺多的……
代码
#include <bits/stdc++.h>
//#define ivorysi
#define MAXN 100005
#define mo 974711
#define INF 1000000000000000000LL
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long int64;
pii poi[MAXN * 26];
vector<int> V[MAXN],st;
int N,M,c,cnt,T;
struct Hash {
struct node {
int64 x;int next,c;
}E[MAXN * 26];
int head[mo + 5],sumE;
void clear() {
sumE = 0;memset(head,0,sizeof(head));
}
void add(int64 x,int c) {
int u = x % mo;
E[++sumE].x = x;E[sumE].next = head[u];E[sumE].c = c;head[u] = sumE;
}
void Insert(pii x,int c) {
add(1LL * (x.fi - 1) * M + x.se,c);
}
int Query(pii x) {
int u = (1LL * (x.fi - 1) * M + x.se) % mo;
for(int i = head[u] ; i ; i = E[i].next) {
if(E[i].x == 1LL * (x.fi - 1) * M + x.se) return E[i].c;
}
return -1;
}
}H;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
struct node {
int to,next;
}edge[MAXN * 100];
int head[MAXN * 26],sumE,low[MAXN * 26],dfn[MAXN * 26],idx,col[MAXN * 26],tot;
bool fir[MAXN * 26];
void dfs(int u,int fa) {
dfn[u] = low[u] = ++idx;
col[u] = tot;
int son = 0;
for(int i = head[u] ; i ; i = edge[i].next) {
int v = edge[i].to;
if(v != fa) {
if(dfn[v]) low[u] = min(low[u],dfn[v]);
else {
++son;
dfs(v,u);
low[u] = min(low[u],low[v]);
if(fa != 0 && low[v] >= dfn[u]) {
st.push_back(u);
}
}
}
}
if(!fa && son > 1) st.push_back(u);
}
void add(int u,int v) {
edge[++sumE].to = v;
edge[sumE].next = head[u];
head[u] = sumE;
}
void Init() {
sumE = 0;
for(int i = 1 ; i <= cnt ; ++i) {
head[i] = dfn[i] = low[i] = col[i] = fir[i] = tot = idx = 0;
}
H.clear();
int u,v;
for(int i = 1 ; i <= c ; ++i) {
scanf("%d%d",&u,&v);
poi[i] = make_pair(u,v);
H.Insert(poi[i],i);
}
cnt = c;
for(int i = 1 ; i <= c ; ++i) {
V[i].clear();
for(int x = -2 ; x <= 2 ; ++x) {
for(int y = -2 ; y <= 2 ; ++y) {
if(x == 0 && y == 0) continue;
pii tmp = make_pair(poi[i].fi + x,poi[i].se + y);
if(tmp.fi < 1 || tmp.fi > N || tmp.se < 1 || tmp.se > M) continue;
if(H.Query(tmp) == -1) {
poi[++cnt] = tmp;
H.Insert(poi[cnt],cnt);
}
if(x <= 1 && x >= -1 && y <= 1 && y >= -1) fir[H.Query(tmp)] = 1;
V[i].push_back(H.Query(tmp));
}
}
}
for(int i = c + 1 ; i <= cnt ; ++i) {
for(int j = 0 ; j <= 3 ; ++j) {
pii tmp = make_pair(poi[i].fi + dx[j],poi[i].se + dy[j]);
if(tmp.fi < 1 || tmp.fi > N || tmp.se < 1 || tmp.se > M) continue;
int x = H.Query(tmp);
if(x <= c) continue;
add(i,x);
}
}
}
void Solve() {
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&N,&M,&c);
Init();
if(1LL * N * M - c <= 1) {puts("-1");goto again;}
if(c == 0) {
if(1LL * N * M == 2) puts("-1");
else if(N == 1 || M == 1) puts("1");
else puts("2");
goto again;
}
st.clear();
for(int i = c + 1 ; i <= cnt ; ++i) {
if(!dfn[i]) {
++tot;
dfs(i,0);
}
}
for(int i = 1 ; i <= c ; ++i) {
int t = 0;
for(auto k : V[i]) {
if(k <= c) continue;
if(k > c) {
if(t == 0) t = col[k];
else if(t != col[k]) {
puts("0");
goto again;
}
}
}
}
if(1LL * N * M - c == 2) {puts("-1");goto again;}
for(auto k : st) {
if(fir[k]) {puts("1");goto again;}
}
if(M == 1 || N == 1) puts("1");
else puts("2");
again:;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}