这个题目用tarjan找联通块，缩点，然后统计出入度为0的点理论上是可行的，但问题是会暴栈。考虑到这个题目的特殊性，可以直接用一次bfs找到数字相同且联通的块，这就是一个联通块，然后缩点，统计出入度即可。
#include#include #include #include using namespace std; const int maxn=1e3+9; int a[maxn][maxn]; int con; int ss[maxn*maxn],in[maxn*maxn],out[maxn*maxn]; int n,m; struct { int t,s; }que[maxn*maxn]; bool text[maxn*maxn]; void bfs() { con=0; memset(text,0,sizeof(text)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!text[i*m+j]) { int front=1,end=0; que[++end].t=i; que[end].s=j; text[i*m+j]=1; while(front<=end) { int t=que[front].t,s=que[front++].s; for(int p=-1;p<=1;p++) for(int q=-1;q<=1;q++) if(fabs(p)+fabs(q)==1&&t+p>=1&&t+p<=n&&s+q>=1&&s+q<=m) if(a[t][s]==a[t+p][s+q]) if(!text[(t+p)*m+s+q]) { text[(t+p)*m+s+q]=1; que[++end].t=t+p; que[end].s=s+q; } } con++; for(int i=1;i<=end;i++) { ss[que[i].t*m+que[i].s]=con; } } } int main() { // freopen("in.txt","r",stdin); while(scanf("%d %d",&m,&n)!=EOF) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); bfs(); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int p=-1;p<=1;p++) for(int q=-1;q<=1;q++) if(fabs(p)+fabs(q)==1&&i+p> =1&&i+p<=n&&j+q>=1&&j+q<=m) if(a[i][j]>=a[i+p][j+q]) if(ss[(i+p)*m+j+q]!=ss[i*m+j]) { in[ss[(i+p)*m+j+q]]++; out[ss[i*m+j]]++; } int ansin=0,ansout=0,ans; for(int i=1;i<=con;i++) { if(in[i]==0) ansin++; if(out[i]==0) ansout++; } ans=max(ansin,ansout); if(con<=1) printf("0\n"); else printf("%d\n",ans); } return 0; }