简单 强连通分量 。

稍微看一下题，易知此题是在求让所有的方格都可以互相通行，这样我们就知道此题正解强连通分量和缩点。

此题先要知道强连通分量板子怎么写。

此外，我们一般不用邻接矩阵存储图，一般用链式前向星或 vector 存储图，这样此题需要二维转一维。精确来说，需要对一个格子上下左右四个方向进行连边，这样就可以转成一维了。

板子打完后，我们需要进行缩点，然后统计一下每一个强连通分量的出度和入度，然后统计出度和入度为 0 的个数取一个最大值即可。

三个重点：

1. 有一种特殊情况，所有边都连通时，无需加缆车，就直接输出 0。

2. 对于出度和入度为 0 的强连通分量个数，我们一定要加缆车。因为当一个强连通分量入度为 0 是，别的强连通分量无法进入此强连通分量，故要统计。而当一个强连通分量出度为 0 时，此强连通分量无法进入别的强连通分量，故要统计。易知最后需要取一个最大值。

3. 强连通分量必须是有向边，而此题正好是有向边。当相邻格子高度相等时，他们俩一定在一个强连通分量中，无需考虑。而高度不等时，只有从高往低连，不能从低往高连。综上是有向边。

AC CODE

#include<cstdio>
#include<algorithm>
using namespace std;
inline int in(){
	int x=0,f=1;char c;
	c=getchar();
	while (c<'0'||c>'9'){
		if (c=='-')f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int dfn[250005],low[250005],cnt,s[250005],top,f[250005],tot,ru[250005],chu[250005];
int head[500005],id,n,m,ans1,ans2,a[505][505];
struct node{int to,nex;}w[1000005];//记得开四倍空间，上下左右都要加边
bool vis[250005];
inline void add(int x,int y,int xx,int yy){
	if (xx<1||yy<1||xx>n||yy>m||a[x][y]<a[xx][yy])return ;
	int u=(x-1)*m+y,v=(xx-1)*m+yy;//二维转一维
   	w[++id].to=v;
    w[id].nex=head[u];
    head[u]=id;
}
inline void Tarjan(int x){//Tarjan 板子
	low[x]=dfn[x]=++cnt;
	vis[x]=1;
	s[++top]=x;
	for (int i=head[x];i;i=w[i].nex){
		int y=w[i].to;
		if (!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if (vis[y])low[x]=min(low[x],low[y]);
	}
	if (dfn[x]==low[x]){
		int y;tot++;
        do{
        	y=s[top--];
            f[y]=tot;
            vis[y]=0;
        }while(x!=y);
	}
}
int main(){
	m=in(),n=in();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			a[i][j]=in();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			add(i,j,i,j-1);
			add(i,j,i,j+1);
			add(i,j,i-1,j);
			add(i,j,i+1,j);
		}
	n*=m;
	for (int i=1;i<=n;i++)if (!dfn[i])Tarjan(i);
	if (tot==1){puts("0");return 0;}//特判
	for (int i=1;i<=n;i++)
		for (int j=head[i];j;j=w[j].nex){
			int tmp=w[j].to;
			if (f[i]!=f[tmp])ru[f[i]]=1,chu[f[tmp]]=1;//统计每个强连通分量的入度和出度
		}
	for (int i=1;i<=tot;i++){//统计入度和出度为 0 的个数
		if (!ru[i])ans1++;
		if (!chu[i])ans2++;
	}
	printf ("%d",max(ans1,ans2));//取最大值
	return 0;
}

// SCC 缩点 Tarjan 算法 O(N)
#include<bits/stdc++.h>
using namespace std;

const int N=250005,M=4*N;
int to[M],ne[M],h[N],idx;
void add(int a,int b){
  to[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
int n,m,a[505][505];
int dfn[N],low[N],stk[N],top,scc[N],cnt;
int in[N],out[N],s1,s2;

int get(int i,int j){return (i-1)*m+j;} //格点的编号
void ade(int i,int j){
  if(i>1){
    if(a[i][j]>=a[i-1][j]) add(get(i,j),get(i-1,j)); //向上连边
    if(a[i][j]<=a[i-1][j]) add(get(i-1,j),get(i,j)); //向下连边
  }
  if(j>1){
    if(a[i][j]>=a[i][j-1]) add(get(i,j),get(i,j-1)); //向左连边
    if(a[i][j]<=a[i][j-1]) add(get(i,j-1),get(i,j)); //向右连边
  }
}

void tarjan(int x){ //SCC缩点
  dfn[x]=low[x]=++dfn[0]; stk[++top]=x;
  for(int i=h[x];i;i=ne[i]){
    int y=to[i];
    if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
    else if(!scc[y]) low[x]=min(low[x],dfn[y]); 
  }

  if(dfn[x]==low[x]){
    ++cnt;
    while(stk[top+1]!=x) scc[stk[top--]]=cnt; //缩点的编号
  }
}

int main(){
  scanf("%d%d",&m,&n); //m列n行
  for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
    scanf("%d",&a[i][j]),ade(i,j); //连边
    
  for(int i=1;i<=n*m;++i) if(!dfn[i]) tarjan(i); 
  
  for(int i=1;i<=n*m;++i)for(int j=h[i];j;j=ne[j]) //枚举每个格点的出边
    if(scc[i]!=scc[to[j]]) ++in[scc[to[j]]],++out[scc[i]];
    
  for(int i=1;i<=cnt;++i){
    if(!in[i]) ++s1;  //入度为0的缩点个数
    if(!out[i]) ++s2; //出度为0的缩点个数
  }
  printf("%d",cnt==1?0:max(s1,s2));
  return 0;
}