解析

看起來很不碼農但寫起來其實還行的一道題。
主要也是因為我賀題解把所有的雷都避過去了

首先一個比較顯然的結論是：通過堵角上的，答案不超過2。
所以本題只要把答案是-1，0，1，2的情況判出來即可。

-1是只有一個空位或只有兩個相鄰空位。
0是原圖不連通。
1是原圖存在割點。
其他都是2。

做完了？太天真了。

$n,m\le 10^9$

那咋辦？
注意到，$c\le 10^5$，這張圖非常稀疏，在空網格上暴力tarjan看起來非常的蠢。
那怎么辦？
我們嘗試對于每個蛐蛐，提取出它周圍的格子，這樣的節點數就變成了 $O(c)$ 級別。（感覺有些像華容道那個題）
然后在新的圖上tarjan就好了。

還要注意億點點坑點：

提出的“周圍一圈”應該是 $5\times 5$ 而不是 $3\times 3$，同時只有距離最近蛐蛐曼哈頓距離為1的點是割點才算割點。

判聯通的時候要把8聯通的蛐蛐全找出來一起判。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=1e5+100;const int mod=1333331; const double inf=1e9; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,c; bool flag=0;struct node{int to,nxt; }p[N*25*4*2]; int fi[N*25],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; }struct Hash{node p[N*25];int fi[mod+1],tot,cnt;ll key[N*25];int id[N*25];void ins(int x,int y,int Id){ll w=1ll*x*(m+1)+y,o=w%mod;++tot;id[tot]=Id;key[tot]=w; p[++cnt]=(node){tot,fi[o]};fi[o]=cnt;//debug("add o=%lld fi=%d\n",o,fi[o]);}int find(int x,int y){ll w=1ll*x*(m+1)+y,o=w%mod;for(int i=fi[o];~i;i=p[i].nxt){//debug("o=%lld i=%d\n",o,i);//ok;if(key[p[i].to]==w) return id[p[i].to];}return 0;}void init(){tot=0;memset(fi,-1,sizeof(fi));cnt=-1;} }mp;int tot;int x[N],y[N]; bool jd[N*25]; int d24x[25]={0,-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2},d24y[25]={0,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2}; int d8x[9]={0,-1,-1,-1,0,0,1,1,1},d8y[9]={0,-1,0,1,-1,1,-1,0,1}; int d4x[5]={0,-1,0,0,1},d4y[5]={0,0,-1,1,0};int cut; int dfn[N*25],low[N*25],tim,bel[N*25],Id; void tarjan(int x,int rt=0){dfn[x]=low[x]=++tim;bel[x]=Id;int son(0);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;//if(to<=c) continue;if(!dfn[to]){tarjan(to);son++;if(low[to]>=dfn[x]){cut+=jd[x];}low[x]=min(low[x],low[to]);}else low[x]=min(low[x],dfn[to]);}if(rt&&son==1) cut-=jd[x];return; }bool vis[N]; int nowId; void dfs(int x,int y){int now=mp.find(x,y);vis[now]=1;for(int d=1;d<=8;d++){int nx=x+d8x[d],ny=y+d8y[d];if(nx<1||nx>n||ny<1||ny>m) continue;int to=mp.find(nx,ny);if(to>c){if(nowId==0) nowId=bel[to];else if(nowId!=bel[to]) nowId=-1;}else if(!vis[to]) dfs(nx,ny); } }void clear(){mp.init();memset(fi,-1,sizeof(int)*(tot+1));cnt=-1;memset(jd,0,sizeof(int)*(tot+1));cut=tim=Id=0;memset(dfn,0,sizeof(int)*(tot+1));memset(low,0,sizeof(int)*(tot+1));memset(bel,0,sizeof(int)*(tot+1));memset(vis,0,sizeof(int)*(c+1));tot=0; }void work(){n=read();m=read();tot=c=read();for(int i=1;i<=c;i++){x[i]=read();y[i]=read();mp.ins(x[i],y[i],i); }for(int i=1;i<=c;i++){for(int d=1;d<=24;d++){int nx=x[i]+d24x[d],ny=y[i]+d24y[d];if(nx<1||nx>n||ny<1||ny>m) continue; if(!mp.find(nx,ny)){mp.ins(nx,ny,++tot);int x=tot;for(int d=1;d<=4;d++){int nnx=nx+d4x[d],nny=ny+d4y[d];int to=mp.find(nnx,nny);if(to&&to>c){//printf("d=%d (%d %d) -> (%d %d)\n",d,nx,ny,nnx,nny);addline(x,to);addline(to,x);}}}int to=mp.find(nx,ny);if(to<=c) continue;if(abs(nx-x[i])<=1&&abs(ny-y[i])<=1) jd[to]=1;}}if(flag) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) printf("%d ",mp.find(i,j));puts("");}for(int i=c+1;i<=tot;i++){if(!dfn[i]){++Id;tarjan(i,1);}}if(1ll*n*m-c<2||(1ll*n*m-c==2&&(Id==1||n*m==2))){puts("-1");return;}for(int i=1;i<=c;i++){if(!vis[i]){nowId=0;dfs(x[i],y[i]);if(nowId==-1){puts("0");return;}}}if(cut||n==1||m==1) puts("1");else puts("2");return; }signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=-1;int T=read();while(T--){clear();work();}return 0; }

總結

以上是生活随笔為你收集整理的洛谷P1173：[NOI2016] 网格（tarjan、离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。