Time Limit: 20 Sec
Memory Limit: 256 MB
http://uoj.ac/problem/142
Input
第一行一个正整数 T，表示南瓜灯数目。
对于每一个南瓜灯，第一行是三个整数 n,m,K，表示南瓜灯的大小和被弄坏的格子数。
接下来 K 行每行包含两个整数 x,y（1≤x≤n,1≤y≤m），表示第 x 行第 y 列的格子被弄坏了。
数据保证 n,m≥3，0≤K<nm 且不会重复描述一个被弄坏的格子。
Output
对于每一个南瓜灯，输出一行，如果这个南瓜灯能被做成工艺品，那么输出 "Yes"，否则输出 "No"。
Sample Input
Sample Output
No
Yes
No
题意
给你一个网格，然后有些地方是墙，然后问你空出来的地方，是否能够构成一颗树
注意，左右是相连的
题解：
就暴力就好了，注意如果n*m>3e5 是可以直接判断为no的
所以这个可以拿到很多测试点
代码
#include<iostream> #include<stdio.h> #include<cstring> using namespace std; #define maxn 1005000 int n,m,k,x,y; int fa[maxn]; int vis[maxn]; int fi(int x) { return fa[x]==x?x:fa[x]=fi(fa[x]); } int flag = 0; int tot = 0; void uni(int x,int y) { int p = fi(x); int q = fi(y); if(p==q) flag=1; if(p!=q) { fa[p]=q; tot++; } } int get(int x,int y) { long long p = x*m-m+y; return p>1000000?1000001:p; } int main() { int t;scanf("%d",&t); while(t--) { tot = 0; memset(vis,0,sizeof(vis)); scanf("%d%d%d",&n,&m,&k); if(1ll*n*m>1000000){puts("No");for(int i=1;i<=k;i++)scanf("%d%d",&x,&y);continue;} for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); vis[get(x,y)]=1; } for(int i=1;i<=n*m;i++) fa[i]=i; flag = 0; for(int i=1;i<=n*m;i++) { if(vis[i]==0) { if(i%m==0&&!vis[i-m+1]) uni(i-m+1,i); if(i%m!=1&&!vis[i-1]) uni(i-1,i); if(i>m&&!vis[i-m]) uni(i-m,i); if(flag)break; } if(flag)break; } if(flag||tot+1!=n*m-k) printf("No\n"); else puts("Yes"); } }
原文：http://www.cnblogs.com/qscqesze/p/4929581.html