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

【题目大意】

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

【算法】

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

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

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

【其它】

完美消除序列的性质是:

对于序列中第i个点Vi。

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

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

【CODE】

http://ideone.com/vqJlV

留下评论

您的电子邮箱地址不会被公开。