给定一个弦图,问最少染色数。
对于弦图的一个完美消去序列,从后往前染色,每次染可以染的最小编号的颜色,由完美消去序列的定义,序列任一后缀的点的导出子图中,由该后缀第一个元素及其邻接点导出的子图一定是完全图,所以,序列中某一元素染的颜色编号是该完全图的大小。所以最小染色数小于等于最大团的点数,而显然前者又大于等于后者,故弦图的最小染色数等于最大团的大小。
/**************************************************************
Problem: 1006
User: idy002
Language: C++
Result: Accepted
Time:1672 ms
Memory:11968 kb
****************************************************************/ #include <cstdio>
#include <vector>
#define maxn 10010
using namespace std; int n, m;
vector<int> g[maxn];
bool done[maxn];
int label[maxn], pos[maxn]; int msc() {
int rt = ;
for( int i=n; i>=; i-- ) {
int mu = ;
for( int u=; u<=n; u++ ) {
if( !done[u] ) {
if( !mu || label[u]>label[mu] )
mu = u;
}
}
done[mu] = true;
pos[mu] = i;
int cnt = ;
for( int t=; t<g[mu].size(); t++ ) {
int v = g[mu][t];
if( done[v] ) {
cnt++;
} else {
label[v]++;
}
}
rt = max( rt, cnt+ );
}
return rt;
}
int main() {
scanf( "%d%d", &n, &m );
for( int i=,u,v; i<=m; i++ ) {
scanf( "%d%d", &u, &v );
g[u].push_back(v);
g[v].push_back(u);
}
printf( "%d\n", msc() );
}