代码：http://www.lydsy.com/JudgeOnline/problem.php?id=1006
弦图的最小染色，详见CDQ的09年WC论文《弦图与区间图》。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define AddEdge( s , t ) Add( s , t ) , Add( t , s )
#define MAXN 10100
#define inf 0x7fffffff
struct edge {
edge *next ;
int t ;
} *head[ MAXN ] ;
void Add( int s , int t ) {
edge *p = new( edge ) ;
p -> t = t , p -> next = head[ s ] ;
head[ s ] = p ;
}
int n , m , ans = 0 , c[ MAXN ] , l[ MAXN ] ;
bool f[ MAXN ] , F[ MAXN ] ;
int main( ) {
scanf( "%d%d" , &n , &m ) ;
memset( head , 0 , sizeof( head ) ) ;
while ( m -- ) {
int s , t ; scanf( "%d%d" , &s , &t ) ;
AddEdge( s , t ) ;
}
memset( f , false , sizeof( f ) ) ;
memset( l , 0 , sizeof( l ) ) ;
for ( int i = 0 ; i ++ < n ; ) {
int rec = - inf , ret ;
for ( int j = 0 ; j ++ < n ; ) if ( ! f[ j ] && l[ j ] > rec ) {
rec = l[ j ] , ret = j ;
}
for ( int j = 0 ; j ++ < n ; ) F[ j ] = true ;
f[ ret ] = true ;
for ( edge *p = head[ ret ] ; p ; p = p -> next ) if ( ! f[ p -> t ] ) {
l[ p -> t ] ++ ;
} else {
F[ c[ p -> t ] ] = false ;
}
for ( int j = 0 ; j ++ < n ; ) if ( F[ j ] ) {
c[ ret ] = j , ans = max( ans , j ) ;
break ;
}
}
printf( "%d\n" , ans ) ;
return 0 ;
}
