首页 > 代码库 > 关于弦图一些问题的解法

关于弦图一些问题的解法

完美消除序列($MCS$算法):

每个点记录一个势,表示与它相邻的已经在完美消除序列的点的个数。

先把$n$号点弄出来,然后每次把势最大的弄出来,这样依次求出的点的逆序就是完美消除序列,使用链表或动态数组可以让复杂度降至$O(n)$

 

代码: 

1 for (RG int i=1;i<=n;++i) ep[0].push_back(i);2 for (RG int i=n,now;i;--i){3     while (1){4     now=ep[best].back(); if (!l[now]) break;5     ep[best].pop_back(); while (ep[best].empty()) --best;6     }7     l[now]=i,p[i]=now;8  }

 

最小染色:求出完美消除序列以后逆序把当前点设一个与相邻点都不同的颜色。

最大独立集:求出完美消除序列以后从前往后能选则选。

最小团覆盖:最大独立集=最小团覆盖。

极大团:还没看懂。。

区间图和完美图以后再补。。

关于弦图一些问题的解法