给定一张 $n \times m$ 的网格图，其中每行为一个圈，即 $(x, 1)$ 和 $(x, m)$ 视为相邻。
现在在网格图中删去指定的 $K$ 个点 (以及与它们关联的边)，判断剩下的图是否为一棵树。
第一行包含一个正整数 $T$ ($T \leq 10$)，表示数据组数。
对于每组数据，第一行包含三个整数 $n, m, K$ ($3 \leq n, m \leq 10^9; 0 \leq K \leq \min \{nm-1, 10^5\}$)，表示网格图的大小和删去点的个数。
接下来 $K$ 行，每行包含两个整数 $x, y$ ($1 \leq x \leq n; 1 \leq y \leq m$），表示第 $x$ 行第 $y$ 列的点被删去了。保证同一个点至多被描述一次。
对于每组数据，输出一行，如果剩下的图为一棵树，那么输出 "Yes"，否则输出 "No"。
由于一个点至多出现一次，因此我们可以直接计算出最终图的点数和边数上界。
点数很简单，即 $|V| = n m - K$。
至于边数的话，由于原图共有 $n m$ 条横向边和 $(n-1) m$ 条纵向边，故有 $(2n-1) m$ 条边。而每删去一个点至多删去 $4$ 条边，因此 $|E| \geq (2n-1) m - 4K$。
由于树需要满足 $|E| = |V| - 1$，因此有 $nm - K - 1 = |E| \geq (2n-1) m - 4K$，这等价于 $3 K \geq (n-1) m + 1$。
因此如果 $n, m$ 不满足上述条件的话，直接返回 No。
如果 $n, m$ 满足上述条件，由于 $n \geq 3 \Rightarrow n \leq \dfrac 32 (n-1)$，因此 $|V| < n m \leq \dfrac 32 (n-1) m < \dfrac 92 K \leq 4.5 \times 10^5$。
即点数不超过 $4.5 \times 10^5$，故直接使用 dfs 或并查集判断是否为树即可。
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0};
int n, m, k;
int forbid[N], used[N];
inline int get(int r, int c) {return (r - 1) * m + c;}
bool dfs(int r, int c, int la = 0) {
int d, nr, nc, cur, nxt;
used[cur = get(r, c)] = 1;
for (d = 0; d < 4; ++d) {
nr = r + dr[d]; nc = (c + dc[d] + m - 1) % m + 1; nxt = get(nr, nc);
if (1 <= nr && nr <= n && !forbid[nxt] && nxt != la)
if (used[nxt] || !dfs(nr, nc, cur)) return false;
}
return true;
}
bool work() {
int i, j = 0, u, v;
scanf("%d%d%d", &n, &m, &k);
if (3 * k <= (n - 1ll) * m) {for (++k; k; --k) gets((char*)used); return false;}
memset(forbid, 0, sizeof forbid);
memset(used, 0, sizeof used);
for (i = 0; i < k; ++i) scanf("%d%d", &u, &v), forbid[get(u, v)] = 1;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j)
if (!(forbid[get(i, j)] || used[get(i, j)])) {
if (!dfs(i, j)) return false; break;
}
if (j <= m) break;
}
for (i = get(i, j); i <= n * m; ++i)
if (!(forbid[i] || used[i])) return false;
return true;
}
int main() {
int T;
for (scanf("%d", &T); T; --T) puts(work() ? "Yes" : "No");
return 0;
}
坑1：不满足条件输出 No 时记得把剩下 $k$ 行数据读进来。
坑2：dfs 时注意父子边不能算入环，还有原图的行为一个圈，需要注意。