[BZOJ1006 [HNOI2008]神奇的国度]【弦图】

【题目大意】

给一个弦图。问色数是多少。

【算法】

先是有显然的定理：色数(用最少种颜色涂满图中的点，使得每条边两端的点颜色都不同)>=团数(最大团的点数)

因为是弦图，由完美消除序列的性质可以构造得色数=团数，于是达到下界。

于是直接利用完美消除序列的性质求出团数即可。

【其它】

完美消除序列的性质是：

对于序列中第i个点Vi。

令S={Vj | (j>i) && ((Vi,Vj) in E)}，那么S+Vi成一个团。

>.<还是V^2。虽然O(V+E)也不难写。求不鄙视。

【CODE】

http://ideone.com/vqJlV