学步园

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.

传送门：【POJ】Popular Cows

题目大意：有n头牛，再给m个关系，每个关系(u,v)表示u崇拜v，如果u崇拜v，v崇拜w，则说u崇拜w，现在问有多少的牛被其他所牛的牛崇拜。

题目分析：强连通缩点。缩点前判断图是否连通，如果不连通，输出0。否则，缩点。看缩点后是否有多于1个分量的出度等于0，有，输出0。否则，计算所有牛中属于的分量出度为0的个数，输出即可。

代码如下：

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

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

const int MAXN = 10005 ;
const int MAXE = 50005 ;

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] ;
	
	void init () {
		top = 0 ;
		cntE = 0 ;
		scc_cnt = 0 ;
		dfs_clock = 0 ;
		clear ( ou , 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 ) {
		REPF ( i , 1 , n )
			if ( !Dfn[i] )
				Tarjan ( i ) ;
	}
	
	void solve ( int n ) {
		REPF ( u , 1 , 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 ;
				}
			}
		int num = 0 , cnt = 0 ;
		REPF ( i , 1 , scc_cnt )
			if ( !ou[i] )
				++ cnt ;
		if ( cnt > 1 ) {
			printf ( "0\n" ) ;
			return ;
		}
		REPF ( i , 1 , n )
			if ( !ou[scc[i]] )
				++ num ;
		printf ( "%d\n" , num ) ;
	}
} ;

SCC C ;
int p[MAXN] ;

int find ( int x ) {
	int o = x , ans , tmp ;
	while ( p[o] != o )
		o = p[o] ;
	ans = o ;
	o = x ;
	while ( p[o] != o ) {
		tmp = p[o] ;
		p[o] = ans ;
		o = tmp ;
	}
	return ans ;
}

void work () {
	int n , m ;
	int u , v ;
	while ( ~scanf ( "%d%d" , &n , &m ) && n ) {
		C.init () ;
		REPF ( i , 1 , n )
			p[i] = i ;
		while ( m -- ) {
			scanf ( "%d%d" , &u , &v ) ;
			C.addedge ( u , v ) ;
			int x = find ( u ) ;
			int y = find ( v ) ;
			p[x] = y ;
		}
		REPF ( i , 1 , n )
			p[i] = find ( i ) ;
		int flag = 0 ;
		REPF ( i , 2 , n )
			if ( p[i] != p[i - 1] )
				flag = 1 ;
		if ( flag ) {
			printf ( "0\n" ) ;
			continue ;
		}
		C.find_scc ( n ) ;
		C.solve ( n ) ;
	}
}

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