P1653

ryf_loser · 2023-08-30 11:59:20 · 题解

简单 强连通分量 。

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

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

此外，我们一般不用邻接矩阵存储图，一般用链式前向星或 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;
}