学步园

FR's ski area is a rectangle of width W and length L of 'land squares' (1 <= W <= 500; 1 <= L <= 500). Each land square is an integral height H above sea level (0 <= H <= 9,999). Cows can ski horizontally and vertically between any two adjacent land squares,
but never diagonally. Cows can ski from a higher square to a lower square but not the other way and they can ski either direction between two adjacent squares of the same height.

FR wants to build his ski area so that his cows can travel between any two squares by a combination of skiing (as described above) and ski lifts. A ski lift can be built between any two squares of the ski area, regardless of height. Ski lifts are bidirectional.
Ski lifts can cross over each other since they can be built at varying heights above the ground, and multiple ski lifts can begin or end at the same square. Since ski lifts are expensive to build, FR wants to minimize the number of ski lifts he has to build
to allow his cows to travel between all squares of his ski area.

Find the minimum number of ski lifts required to ensure the cows can travel from any square to any other square via a combination of skiing and lifts.

* Lines 2..L+1: L lines, each with W space-separated integers corresponding to the height of each square of land.

OUTPUT DETAILS:

FR builds the three lifts. Using (1, 1) as the lower-left corner,
the lifts are (3, 1) <-> (8, 2), (7, 3) <-> (5, 2), and (1, 3) <->
(2, 2). All locations are now connected. For example, a cow wishing
to travel from (9, 1) to (2, 2) would ski (9, 1) -> (8, 1) -> (7,
1) -> (7, 2) -> (7, 3), take the lift from (7, 3) -> (5, 2), ski
(5, 2) -> (4, 2) -> (3, 2) -> (3, 3) -> (2, 3) -> (1, 3), and then
take the lift from (1, 3) - > (2, 2). There is no solution using
fewer than three lifts.

传送门：【POJ】2375 Cow Ski Area

题目分析：强连通缩点，求出分量入度为0的个数a，出度为0的个数b，答案即max{a,b}。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int MAXN = 260000 ;
const int MAXE = 1200000 ;
const int MAXG = 505 ;

struct Edge {
	int v , n ;
	Edge ( int var = 0 , int next = 0 ) : v(var) , n(next) {}
} ;

struct SCC {
	Edge edge[MAXE] ;
	int adj[MAXN] , cntE ;
	int Dfn[MAXN] , Low[MAXN] , dfs_clock ;
	int scc[MAXN] , scc_cnt ;
	int S[MAXN] , top ;
	bool ins[MAXN] ;
	bool ou[MAXN] , in[MAXN] ;
	
	void init () {
		top = 0 ;
		cntE = 0 ;
		scc_cnt = 0 ;
		dfs_clock = 0 ;
		clear ( ou , 0 ) ;
		clear ( in , 0 ) ;
		clear ( ins , 0 ) ;
		clear ( Dfn , 0 ) ;
		clear ( adj , -1 ) ;
	}
	
	void addedge ( int u , int v ) {
		edge[cntE] = Edge ( v , adj[u] ) ;
		adj[u] = cntE ++ ;
	}
	
	void Tarjan ( int u ) {
		Dfn[u] = Low[u] = ++ dfs_clock ;
		S[top ++] = u ;
		ins[u] = 1 ;
		for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
			int v = edge[i].v ;
			if ( !Dfn[v] ) {
				Tarjan ( v ) ;
				Low[u] = min ( Low[u] , Low[v] ) ;
			}
			else if ( ins[v] )
				Low[u] = min ( Low[u] , Dfn[v] ) ;
		}
		if ( Low[u] == Dfn[u] ) {
			++ scc_cnt ;
			while ( 1 ) {
				int v = S[-- top] ;
				ins[v] = 0 ;
				scc[v] = scc_cnt ;
				if ( v == u )
					break ;
			}
		}
	}
	
	void find_scc ( int n ) {
		REP ( i , n )
			if ( !Dfn[i] )
				Tarjan ( i ) ;
	}
	
	void solve ( int n ) {
		REP ( u , n )
			for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
				int v = edge[i].v ;
				if ( scc[u] != scc[v] ) {
					ou[scc[u]] = 1 ;
					in[scc[v]] = 1 ;
				}
			}
		int cnt_in = 0 , cnt_ou = 0 ;
		REPF ( i , 1 , scc_cnt ) {
			if ( !ou[i] )
				++ cnt_ou ;
			if ( !in[i] )
				++ cnt_in ;
		}
		printf ( "%d\n" , max ( cnt_in , cnt_ou ) ) ;
	}
} ;

SCC C ;
int G[MAXG][MAXG] ;

void work () {
	int n , m ;
	int u , v ;
	while ( ~scanf ( "%d%d" , &m , &n ) ) {
		C.init () ;
		REP ( i , n )
			REP ( j , m )
				scanf ( "%d" , &G[i][j] ) ;
		REP ( i , n )
			REP ( j , m ) {
				int ij = i * m + j ;
				if ( i > 0 && G[i][j] >= G[i - 1][j] )
					C.addedge ( ij , ij - m ) ;
				if ( j > 0 && G[i][j] >= G[i][j - 1] )
					C.addedge ( ij , ij - 1 ) ;
				if ( i < n - 1 && G[i][j] >= G[i + 1][j] )
					C.addedge ( ij , ij + m ) ;
				if ( j < m - 1 && G[i][j] >= G[i][j + 1] )
					C.addedge ( ij , ij + 1 ) ;
			}
		C.find_scc ( n * m ) ;
		if ( C.scc_cnt == 1 ) {
			printf ( "0\n" ) ;
			continue ;
		}
		C.solve ( n * m ) ;
	}
}

int main () {
	work () ;
	return 0 ;
}