题目地址：POJ 2375

对每一个点向与之相邻并h小于该点的点加有向边。

然后强连通缩点。问题就转化成了最少加几条边使得图为强连通图，取入度为0和出度为0的点数的较大者就可以。注意，当强连通分量仅仅有一个的时候。答案是0，而不是1.

代码例如以下：

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

using namespace std;

#define LL long long

#define pi acos(-1.0)

const int mod=1e9+7;

const int INF=0x3f3f3f3f;

const double eqs=1e-9;

const int MAXN=250000+10;

int head[MAXN], Ecnt, top, indx, scc;

int low[MAXN], dfn[MAXN], belong[MAXN], instack[MAXN], stk[MAXN], out[MAXN], in[MAXN];

int mp[600][600];

int jx[]={0,0,1,-1};

int jy[]={1,-1,0,0};

struct node

{

        int u, v, next;

}edge[1000000];

void add(int u, int v)

{

        edge[Ecnt].v=v;

        edge[Ecnt].next=head[u];

        head[u]=Ecnt++;

}

void tarjan(int u)

{

        low[u]=dfn[u]=++indx;

        instack[u]=1;

        stk[++top]=u;

        for(int i=head[u];i!=-1;i=edge[i].next){

                int v=edge[i].v;

                if(!dfn[v]){

                        tarjan(v);

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

                }

                else if(instack[v]){

                        low[u]=min(low[u],dfn[v]);

                }

        }

        if(low[u]==dfn[u]){

                scc++;

                while(1){

                        int v=stk[top--];

                        belong[v]=scc;

                        instack[v]=0;

                        if(u==v) break;

                }

        }

}

void init()

{

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

        memset(dfn,0,sizeof(dfn));

        memset(instack,0,sizeof(instack));

        memset(in,0,sizeof(in));

        memset(out,0,sizeof(out));

        Ecnt=top=indx=scc=0;

}

int main()

{

        int n, m, i, j, k, a, b, cntin, cntout;

        init();

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

        for(i=0;i<m;i++){

                for(j=0;j<n;j++){

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

                }

        }

        for(i=0;i<m;i++){

                for(j=0;j<n;j++){

                        for(k=0;k<4;k++){

                                a=i+jx[k];

                                b=j+jy[k];

                                if(a>=0&&a<m&&b>=0&&b<n&&mp[a][b]<=mp[i][j]){

                                        add(i*n+j,a*n+b);

                                }

                        }

                }

        }

        for(i=0;i<n*m;i++){

                if(!dfn[i])

                        tarjan(i);

        }

        if(scc==1){

                printf("0\n");

                return 0;

        }

        for(i=0;i<n*m;i++){

                for(j=head[i];j!=-1;j=edge[j].next){

                        int v=edge[j].v;

                        if(belong[i]!=belong[v]){

                                out[belong[i]]++;

                                in[belong[v]]++;

                        }

                }

        }

        cntin=cntout=0;

        for(i=1;i<=scc;i++){

                if(!in[i]) cntin++;

                if(!out[i]) cntout++;

        }

        printf("%d\n",max(cntin,cntout));

        return 0;

}