传送门：【HDU】3639 Hawk-and-Chicken

题目大意：
n个小朋友要玩老鹰捉小鸡，每个人都有一种手帕，他们之间可能会出现，a给b手帕，b给c手帕，这样，相当于b得到了a的手帕，c得到了a和b的手帕，也就是具有传递性。得到不同种类的手帕最多的将会成为赢家，如果多个人同时最多，那他们都是赢家。现在给你m个行为(u,v)表示u给了v手帕(u != v)，问赢家最多能得到的手帕种类是多少（不包括自己的手帕）以及有哪些人是赢家。(2 <= n <= 5000 , 0 < m <= 30000)。

题目分析：
首先强连通缩点，将所有的强连通分量缩点构成DAG图，每个DAG图上的点的权值表示相应的强连通分量缩点前的个数。然后因为得到手帕种类最多的一定是出度为0 的（假设出度不为0的人u得到最多，那么一定有个人v被u给了手帕，必定v得到的手帕种类比u多，假设矛盾，得证）。那么为了方便统计，直接将图逆转（也就是u->v变成v->u）。然后在逆图上对入度为0的点（也就是原DAG图出度为0的点）做DFS，将路上途经的所有点的权值都加上，最后该点的权值就是包括该点所有遇到的点的权值之和-1（-1是因为要排除自己）。
这样问题基本解决。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( 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 = 5005 ;
const int MAXE = 100000 ;

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

struct SCC {
	Edge edge[MAXE] ;
	int adj[MAXN] , cntE ;
	int Dfn[MAXN] , Low[MAXN] , scc[MAXN] , ins[MAXN] ;
	int S[MAXN] , top ;
	int dfs_clock , scc_cnt ;
	
	void init () {
		top = 0 ;
		cntE = 0 ;
		scc_cnt = 0 ;
		dfs_clock = 0 ;
		CLEAR ( Dfn , 0 ) ;
		CLEAR ( ins , 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 ) ;
	}
} ;

SCC C ;
Edge edge[MAXE] ;
int adj[MAXN] , cntE ;
int in[MAXN] ;
int dp[MAXN] ;
bool vis[MAXN] ;
int cnt[MAXN] ;

void addedge ( int u , int v ) {
	edge[cntE] = Edge ( v , adj[u] ) ;
	adj[u] = cntE ++ ;
}

int dfs ( int u ) {
	int ans = cnt[u] ;
	for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
		int v = edge[i].v ;
		if ( !vis[v] ) {
			ans += dfs ( v ) ;
			vis[v] = 1 ;
		}
	}
	return ans ;
}

void work () {
	int n , m ;
	int u , v ;
	C.init () ;
	scanf ( "%d%d" , &n , &m ) ;
	REP ( i , m ) {
		scanf ( "%d%d" , &u , &v ) ;
		C.addedge ( u , v ) ;
	}
	C.find_SCC ( n ) ;//强连通
	if ( C.scc_cnt == 1 ) {
		printf ( "%d\n" , n - 1 ) ;
		REP ( i , n )
			printf ( "%d%c" , i , i < n - 1 ? ' ' : '\n' ) ;
		return ;
	}
	cntE = 0 ;
	CLEAR ( in , 0 ) ;
	CLEAR ( dp , 0 ) ;
	CLEAR ( cnt , 0 ) ;
	CLEAR ( adj , -1 ) ;
	CLEAR ( vis , 0 ) ;
	REP ( i , n )
		cnt[C.scc[i]] ++ ;//求每个强连通分量的包含结点个数
	REP ( u , n )
		for ( int i = C.adj[u] ; ~i ; i = C.edge[i].n ) {
			int v = C.edge[i].v ;
			if ( C.scc[v] != C.scc[u] ) {
				addedge ( C.scc[v] , C.scc[u] ) ;//建立逆图
				in[C.scc[u]] ++ ;
			}
		}
	REPF ( i , 1 , C.scc_cnt )
		if ( !in[i] ) {//在入度为0的点上DFS
			CLEAR ( vis , 0 ) ;
			dp[i] = dfs ( i ) - 1 ;
		}
	int ans = 0 ;
	REPF ( i , 1 , C.scc_cnt )
		ans = max ( ans , dp[i] ) ;
	printf ( "%d\n" , ans ) ;
	int flag = 0 ;
	REP ( i , n )
		if ( dp[C.scc[i]] == ans ) {
			if ( flag )
				printf ( " " ) ;
			flag = 1 ;
			printf ( "%d" , i ) ;
		}
	printf ( "\n" ) ;
}

int main () {
	int T , cas = 0 ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) {
		printf ( "Case %d: " , ++ cas ) ;
		work () ;
	}
	return 0 ;
}