题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1093
首先缩SCC，然后每个SCC的权就是该SCC的大小，那么最大半连通子图就是图上的一条最长链，那么就在DAG上搞两次拓扑排序就可以啦~
为了防止第二问出错，记得判重边（我偷懒用了SET，感觉越来越依赖STL了。。。）
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <set>
using namespace std ;
#define MAXM 1001000
#define MAXN 100100
struct edge {
edge *next ;
int t ;
} *head[ MAXN ] ;
int n , m , MAX ;
void AddEdge( int s , int t ) {
edge *p = new( edge ) ;
p -> t = t , p -> next = head[ s ] ;
head[ s ] = p ;
}
struct EDGE {
int s , t ;
bool operator < ( const EDGE &a ) const {
return s < a.s || ( s == a.s && t < a.t ) ;
}
bool operator == ( const EDGE &a ) const {
return s == a.s && t == a.t ;
}
bool operator > ( const EDGE &a ) const {
return s > a.s || ( s == a.s && t > a.t ) ;
}
} E[ MAXM ] ;
void Init( ) {
memset( head , 0 , sizeof( head ) ) ;
scanf( "%d%d%d" , &n , &m , &MAX ) ;
for ( int i = 0 ; i ++ < m ; ) {
int s , t ; scanf( "%d%d" , &s , &t ) ; AddEdge( s , t ) ;
E[ i ].s = s , E[ i ].t = t ;
}
}
int dfn[ MAXN ] , low[ MAXN ] , scc[ MAXN ] , Index = 0 , size[ MAXN ] ;
stack < int > Stack ;
bool f[ MAXN ] ;
void dfs( int v ) {
Stack.push( v ) , f[ v ] = true , dfn[ v ] = low[ v ] = ++ Index ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( ! dfn[ p -> t ] ) {
dfs( p -> t ) ; low[ v ] = min( low[ v ] , low[ p -> t ] ) ;
} else if ( f[ p -> t ] ) low[ v ] = min( low[ v ] , low[ p -> t ] ) ;
if ( low[ v ] == dfn[ v ] ) {
size[ v ] = 0 ;
int u ;
do {
u = Stack.top( ) ; Stack.pop( ) , f[ u ] = false ;
size[ scc[ u ] = v ] ++ ;
} while ( u != v ) ;
}
}
set < EDGE > S ;
int NUM[ MAXN ] ;
EDGE make( int s , int t ) {
EDGE u ;
u.s = s , u.t = t ;
return u ;
}
void Tarjan( ) {
memset( dfn , 0 , sizeof( dfn ) ) ;
memset( f , false , sizeof( f ) ) ;
for ( int i = 0 ; i ++ < n ; ) if ( ! dfn[ i ] ) {
dfs( i ) ;
}
S.clear( ) ;
memset( head , 0 , sizeof( head ) ) ;
memset( NUM , 0 , sizeof( NUM ) ) ;
for ( int i = 0 ; i ++ < m ; ) if ( scc[ E[ i ].s ] != scc[ E[ i ].t ] ) {
EDGE u = make( scc[ E[ i ].s ] , scc[ E[ i ].t ] ) ;
if ( S.find( u ) == S.end( ) ) {
S.insert( u ) , AddEdge( u.s , u.t ) ;
NUM[ u.t ] ++ ;
}
}
}
int dp[ MAXN ] , ans = 0 , num[ MAXN ] ;
void Dp( ) {
for ( int i = 0 ; i ++ < n ; ) num[ i ] = NUM[ i ] ;
memset( dp , 0 , sizeof( dp ) ) ;
while ( ! Stack.empty( ) ) Stack.pop( ) ;
for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] && ! num[ i ] ) {
Stack.push( i ) , dp[ i ] = size[ i ] ;
}
while ( ! Stack.empty( ) ) {
int v = Stack.top( ) ; Stack.pop( ) ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) {
dp[ p -> t ] = max( dp[ p -> t ] , dp[ v ] + size[ p -> t ] ) ;
if ( ! ( -- num[ p -> t ] ) ) Stack.push( p -> t ) ;
}
}
for ( int i = 0 ; i ++ < n ; ) ans = max( ans , dp[ i ] ) ;
}
int cnt[ MAXN ] , Cnt = 0 ;
void Count( ) {
for ( int i = 0 ; i ++ < n ; ) num[ i ] = NUM[ i ] ;
memset( cnt , 0 , sizeof( cnt ) ) ;
while ( ! Stack.empty( ) ) Stack.pop( ) ;
for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] && ! num[ i ] ) {
Stack.push( i ) , cnt[ i ] = 1 ;
}
while ( ! Stack.empty( ) ) {
int v = Stack.top( ) ; Stack.pop( ) ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) {
if ( dp[ p -> t ] == dp[ v ] + size[ p -> t ] ) cnt[ p -> t ] += cnt[ v ] , cnt[ p -> t ] %= MAX ;
if ( ! ( -- num[ p -> t ] ) ) Stack.push( p -> t ) ;
}
}
for ( int i = 0 ; i ++ < n ; ) if ( ans == dp[ i ] ) Cnt += cnt[ i ] , Cnt %= MAX ;
}
int main( ) {
Init( ) ;
Tarjan( ) ;
Dp( ) ;
Count( ) ;
printf( "%d\n%d\n" , ans , Cnt ) ;
return 0 ;
}
