题目大意:一个W*L的山，每个山有个高度，当且仅当一个山不比它相邻（有公共边的格子）的山矮时能够滑过去，现在可以装化学电梯来无视山的高度滑雪，问最少装多少电梯使得任意两点都可到达

思路:最后一句话已经把强连通模型裸裸地说出来了 那问题变成了一个图最小加几条边变成强连通图的经典问题，比较一下出度为0和入度为0的点的个数的大小即可，还有个特例只有一个SCC的情况

#include<cstdio>

#include<string.h>

#include<iostream>

#include<algorithm>

#define maxn 6000900

using namespace std;

const int dx[10]={0,0,0,1,-1};

const int dy[10]={0,1,-1,0,0};

int map[509][509];

int head[maxn],next[maxn],point[maxn],now,col,tim;

int dfn[maxn],low[maxn],stack[maxn],top,belong[maxn];

int in[maxn],out[maxn];

bool instack[maxn];

void add(int x,int y)

{

    next[++now]=head[x];

    head[x]=now;

    point[now]=y;

}

void tarjan(int k)

{

    dfn[k]=low[k]=++tim;

    stack[++top]=k;

    instack[k]=1;

    for(int i=head[k];i;i=next[i])

    {

        int u=point[i];

        if(dfn[u]==0)

        {

            tarjan(u);

            low[k]=min(low[k],low[u]);

        }

        else if(instack[u])

        {

            low[k]=min(low[k],low[u]);

        }

    }

    if(dfn[k]==low[k])

    {

        int u;

        ++col;

        do

        {

            u=stack[top--];

            belong[u]=col;

            instack[u]=0;

        }while(u!=k);

    }

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    memset(map,-1,sizeof(map));

    for(int i=1;i<=m;i++)

    {

        for(int j=1;j<=n;j++)

        {

            scanf("%d",&map[i][j]);

        }

    }

    for(int i=1;i<=m;i++)

    {

        for(int j=1;j<=n;j++)

        {

            for(int k=1;k<=4;k++)

            {

                int x=i+dx[k],y=j+dy[k];

                if(map[x][y]!=-1 && map[i][j]>=map[x][y])

                {

                    int xx=(i-1)*n+j,yy=(x-1)*n+y;

                    add(xx,yy);

                }

            }

        }

    }

    for(int i=1;i<=m*n;i++)

    if(dfn[i]==0)tarjan(i);

    if(col==1)

    {

        printf("0\n");

        return 0;

    }

    for(int i=1;i<=m*n;i++)

    {

        for(int j=head[i];j;j=next[j])

        {

            int u=point[j];

            if(belong[i]!=belong[u])

            {

                out[belong[i]]++;

                in[belong[u]]++;

            }

        }

    }

    int zero1=0,zero2=0;

    for(int i=1;i<=col;i++)

    {

        if(in[i]==0)zero1++;

        if(out[i]==0)zero2++;

    }

    printf("%d\n",max(zero1,zero2));

    return 0;

}

POJ 2375 Cow Ski Area【tarjan】