首页 > 代码库 > 关于弦图一些问题的解法
关于弦图一些问题的解法
完美消除序列($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 }
最小染色：求出完美消除序列以后逆序把当前点设一个与相邻点都不同的颜色。
最大独立集：求出完美消除序列以后从前往后能选则选。
最小团覆盖：最大独立集=最小团覆盖。
极大团：还没看懂。。
区间图和完美图以后再补。。
关于弦图一些问题的解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。