学步园

传送门：【POJ】1236 Network of Schools

题目大意：n个学校构成一个有向图，通过m条边连接，一：问至少向图中多少个学校投放软件，可以使得所有学校直接或者间接的通过边（假设存在边(u,v)，则向u投放v可以得到，而向v投放u不能通过v直接得到）得到软件（假设每次投放的软件无穷多）。二：问至少添加多少条边可以使得只用向一个学校投放软件别的学校都能得到软件。

题目分析：其实就是强连通缩点，问一是统计缩点后有多少分量入度为0，问二是指至少添加多少边使得图强连通。然后统计入度为0的点的个数in和出度为0的点的个数ou，则问一输出in，问二如果整个图强连通则输出0，否则输出max{in,ou}。
为什么是max{in,ou}？因为要使得图强连通，则必定每个点的出度以及入度都不为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 = 101 ;
const int MAXE = 10000 ;

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 in[MAXN] , ou[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 ) {
		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 ;
					in[scc[v]] = 1 ;
				}
			}
		int not_in = 0 , not_ou = 0 ;
		REPF ( i , 1 , scc_cnt ) {
			if ( !in[i] )
				++ not_in ;
			if ( !ou[i] )
				++ not_ou ;
		}
		printf ( "%d\n%d\n" , not_in , scc_cnt == 1 ? 0 : max ( not_in , not_ou ) ) ;
	}
} ;

SCC C ;

void work () {
	int n , m , v ;
	while ( ~scanf ( "%d" , &n ) ) {
		C.init () ;
		REPF ( i , 1 , n ) {
			while ( 1 ) {
				scanf ( "%d" , &v ) ;
				if ( !v )
					break ;
				C.addedge ( i , v ) ;
			}
		}
		C.find_scc ( n ) ;
		C.solve ( n ) ;
	}
}

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