前言

这是个什么神仙玩意儿？(仙图 先把结论贴出来方便背板，证明什么的啃完再补 考NOI前千万不要点开什么毒瘤的技能树 所以现在点 由于很懒所以想到哪写到哪

一些约定

G G G无向图 G [ S ] G[S] G[S]点集S的诱导子图 δ ( S ) \delta(S) δ(S)点集S的临集

一些定义

弦

连接环上不相邻两点之间的边

弦图

任意长度>=4的环都有至少一条弦的图 这是弦图，这不是弦图.jpg

单纯点

一个点v是单纯点当且仅当 G [ δ ( v ) ] + v G[\delta(v)]+v G[δ(v)]+v是团

完美消除序列

一个n的排列v1,v2,v3…vn,满足vi在vi,vi+1,vi+2…vn的诱导子图中是一个单纯点

一些性质

弦图的判定

一个图是弦图当且仅当其有完美消除序列

最大势算法(MCS)

每个点有一个标号label[v]，初始label[v]=0 从后往前确定完美消除序列中的每一个元素，每次选择label最大的点v加入序列，并将 δ ( v ) \delta(v) δ(v)中的点的label+1 具体实现可以开n个队列，不需要删除 复杂度O(n+m)

void MCS() {

int mx=0;

fo(i,0,n) lst[i+n+1]=0;

fo(i,1,n) sz[i]=0,vis[i]=0,add(n+1,i);

fd(j,n,1) {

int p=0;

for(++mx;!p;) {

--mx;int Id=mx+n+1;

while (int k=lst[Id]) {

int x=t[k];

lst[Id]=nxt[k];

if (!vis[x]) {

vis[x]=1;