很多分类讨论的题，不对拍很容易被卡正确性。
Description
给一个 $n\times m$ 的网格图，删去其中 $c$ 个点，问再删去至少几个点可以使图上存在两个点不连通。
无法达到目的输出 $-1$。
$n,m\leq10^9,c\leq10^5$。
Solution
首先答案最大是 $2$，删除一个角落相邻的点就可以做到。
玩一玩，答案是 $-1$ 有两种情况：$n\times m-c<2$，或 $n\times m-c=2$ 且剩下的两个点连通。
答案是 $0$ 就是已经存在不连通的两个点。
如果我们把 $n\times m$ 的图建出来，那么答案是 $1$ 就是存在割点。
剩下的答案就是 $2$ 了。
现在问题是图太大，我们需要把这个图缩成 $O(c)$ 个点。
很容易想到周围一大圈都没有被删掉的点的点是没用的，那我们的思路就是把被删掉的点周围的点拉出来建图。
只把周围 $3\times3$ 的点拉出来是不对的，考虑下面这个：
...
..*
...
$(2,2)$ 会成为割点，但实际上它并不是。
所以要拉出来 $5\times5$ 的点，并且只有在 $3\times 3$ 范围内的割点才有效。
然后判断原图是否连通可以用如下的办法：对建出来的图搜连通块，然后把相邻的被删掉的点看作一个整体，如果一组被删掉的点周围四连通的点不属于同一连通块，那么原图就不连通。
最后判断有没有割点用 tarjan 就好了。
复杂度在建图上，如果用哈希表实现，复杂度可以看作 $O(24c)$。
Code
常数巨大，别学。
namespace solve
{
const int maxn = 1e6 + 10;
typedef pair<int, int> pii;
const int dx4[] = {0, 0, 1, -1};
const int dy4[] = {1, -1, 0, 0};
vector<int> e[maxn];
int n, m, c;
inline bool is_in(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }
pii a[maxn], all[maxn];
int cnt;
struct hash_map
{
static const int mod = maxn + -3;
int hash(const pii &x) { return (1ll * x.first * m + x.second) % mod; }
struct node
{
pii x;
int val, nxt;
} a[maxn];
int hd[mod], tot;
int &operator[](const pii &x)
{
int pos = hash(x);
for (int p = hd[pos]; p; p = a[p].nxt)
{
if (x == a[p].x)
{
return a[p].val;
}
}
a[++tot] = {x, 0, hd[pos]}, hd[pos] = tot;
return a[tot].val;
}
int count(const pii &x)
{
int pos = hash(x);
for (int p = hd[pos]; p; p = a[p].nxt)
if (x == a[p].x)
return 1;
return 0;
}
void clear()
{
memset(hd, 0, sizeof(hd)), tot = 0;
}
} mp, mp2;
inline bool has(pii x) { return mp2.count(x); }
inline bool has(int x, int y) { return has(pii(x, y)); }
namespace no_solution
{
bool work()
{
if (1ll * n * m - c <= 1)
return 1;
if (1ll * n * m - c > 2)
return 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!has(i, j))
{
for (int k = 0; k < 4; k++)
{
int nx = i + dx4[k], ny = j + dy4[k];
if (is_in(nx, ny) && !has(nx, ny))
return 1;
}
return 0;
}
return 1;
}
}
namespace ans_eq_zero
{
int father[maxn];
int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); }
void uni(int x, int y) { father[find(x)] = find(y); }
int color[maxn], tot, ucolor[maxn];
void dfs(int x, int col)
{
color[x] = col;
for (int v : e[x])
if (!color[v])
dfs(v, col);
}
bool work()
{
for (int i = 1; i <= cnt; i++)
father[i] = i, color[i] = ucolor[i] = 0;
for (int i = 1; i <= cnt; i++)
if (!color[i])
tot++, dfs(i, tot);
// for (int i = 1; i <= cnt; i++)
// cout << color[i] << " ";
// cout << endl;
for (int i = 1; i <= c; i++)
{
for (int j = 0; j < 4; j++)
{
int x = a[i].first + dx4[j], y = a[i].second + dy4[j];
if (is_in(x, y) && has(x, y))
uni(i, mp2[pii(x, y)]);
}
}
for (int i = 1; i <= c; i++)
{
for (int j = 0; j < 4; j++)
{
int x = a[i].first + dx4[j], y = a[i].second + dy4[j];
if (is_in(x, y) && mp.count(pii(x, y)))
{
int pos = mp[pii(x, y)];
if (!ucolor[find(i)])
ucolor[find(i)] = color[pos];
else if (ucolor[find(i)] != color[pos])
{
// cout << i << " " << x << " " << y << endl;
return 1;
}
}
}
}
return 0;
}
}
int dfn[maxn], low[maxn], son[maxn], tot, cut, cntt;
vector<int> ans;
void tarjan(int x, int fa)
{
dfn[x] = low[x] = ++cntt, son[x] = 0, tot++;
for (int v : e[x])
{
if (!dfn[v])
{
son[x]++;
tarjan(v, x);
low[x] = min(low[x], low[v]);
if (fa != 0 && low[v] >= dfn[x])
cut++, ans.push_back(x);
}
else if (v != fa)
low[x] = min(low[x], dfn[v]);
}
if (fa == 0 && son[x] >= 2)
cut++, ans.push_back(x);
}
int ok[maxn];
void clear()
{
mp.clear(), mp2.clear();
for (int i = 1; i <= cnt; i++)
dfn[i] = low[i] = son[i] = 0, e[i].clear(), ok[i] = 0;
cnt = cntt = 0, tot = cut = 0;
ans.clear();
}
bool check()
{
for (int p : ans)
if (ok[p])
return 1;
return 0;
}
void main()
{
clear();
n = read(), m = read(), c = read();
for (int i = 1; i <= c; i++)
a[i].first = read(), a[i].second = read(), mp2[a[i]] = i;
if (no_solution::work())
{
puts("-1");
return;
}
for (int i = 1; i <= c; i++)
for (int dx = -2; dx <= 2; dx++)
for (int dy = -2; dy <= 2; dy++)
{
int x = a[i].first + dx, y = a[i].second + dy;
if (!is_in(x, y) || has(x, y))
continue;
if (mp.count(pii(x, y)))
{
ok[mp[pii(x, y)]] |= abs(dx) <= 1 && abs(dy) <= 1;
continue;
}
mp[pii(x, y)] = ++cnt, all[cnt] = pii(x, y);
ok[cnt] = (abs(dx) <= 1 && abs(dy) <= 1);
}
// for (int i = 1; i <= cnt; i++)
// {
// cout << i << " " << all[i].first << " " << all[i].second << endl;
// }
if (c == 0)
{
puts((n == 1 || m == 1) ? "1" : "2");
return;
}
for (int i = 1; i <= cnt; i++)
{
for (int j = 0; j < 4; j++)
{
int x = all[i].first + dx4[j], y = all[i].second + dy4[j];
if (is_in(x, y) && mp.count(pii(x, y)))
{
int w = mp[pii(x, y)];
e[i].push_back(w);
e[w].push_back(i);
}
}
}
if (ans_eq_zero::work())
{
puts("0");
return;
}
for (int i = 1; i <= cnt; i++)
if (!dfn[i])
tarjan(i, 0);
if ((cut && check()) || n == 1 || m == 1)
puts("1");
else
puts("2");
}
}