弦：连接环中不想零的两个点的边
弦图：图中任意大小大于 3 的环都至少有一个弦
Fishing Net
判断弦图
Definitions
单纯点： (u) 和 (u) 相邻点集构成的诱导子图是一个团
任意一个弦图至少有一个单纯点。非完全图的弦图至少有两个不相邻的单纯点
完美消除序列： 每次消除一个点，使得这个点在剩下的点的诱导子图中是一个单纯点
图是弦图 (Leftrightarrow) 存在完美消除序列
Brute Force
每次寻找单纯点，然后删掉（(O(n^4))）
找完美消失序列
Algorithm 1 - Lex BFS
从 (n) 到 (1) 给每个点标号。对于每一个点维护一个 list 记录已标号相邻点的标号，标号按字典序排序。每次选择 list 的字典序最大的未标号点标号。
Algorithm 2 - MCS
Maximum Cardinality Search 最大势算法
从 (n o 1) 的顺序给每个点标号。设 (l_i) 表示第 (i) 个点与多少个已标号的店相邻。每次选择 (l_i) 最大的未标号点进行标号。
(O(m+n))
判断是否是完美消失序列
暴力 (O(mn))
优化：设 (v_{i+1dots n}) 中与 (v_i) 相邻的点 (w_1,w_2,dots,w_k)。只需要判断 (w_1) 和 (w_{2dots k}) 是否相邻即可(O(m+n))
模板：SP5446 FISHNET - Fishing Net
int n,m,v[N],ed[N][N],tot,pes[N],pos[N],l[N],t[N];
bool vst[N];
vector<int>e[N];
struct node {
int l,id;
bool operator < (const node &y) const {return l<y.l;}
};
void mcs() {
memset(vst,0,sizeof(vst));
priority_queue<node>q;
rep(i,1,n) ed[i][i]=1, q.push((node){0,i});
tot=n;
while(!q.empty()) {
int u=q.top().id; q.pop();
if(!vst[u]) {
pos[u]=tot, pes[tot--]=u, vst[u]=1;
for(auto v:e[u]) if(!vst[v]) q.push((node){++l[v],v});
}
}
}
bool check() {
memset(vst,0,sizeof(vst));
per(i,n,1) {
int u=pes[i], mp=n, cnt=0;
vst[u]=1;
for(auto v:e[u]) if(vst[v]) mp=min(mp,pos[t[++cnt]=v]);
if(n==mp) continue;
rep(j,1,cnt) if(!ed[pes[mp]][t[j]]) return 0;
}
return 1;
}
int main() {
while((n=read())&&(m=read())) {
memset(e,0,sizeof(e));
memset(ed,0,sizeof(ed));
rep(i,1,m) {
int u=read(), v=read();
e[u].push_back(v), e[v].push_back(u);
ed[u][v]=ed[v][u]=1;
}
mcs();
if(check()) puts("Perfect
");
else puts("Imperfect
");
}
return 0;
}
其他问题
极大团
设第 (i) 个点在弦图的完美消失序列的 (p_i) 个。
设 (N_v={wmid (w,v)in E 且 p_w>p_v})。
则弦图的极大团一定是 (vcup N_v) 的形式。所以最多只有 (n) 个极大团。
接下来要判断 (vcup N_v) 是否是极大团。
设 (A=vcup N_v)，(B=wcup N_w)。则 (A) 不是极大团 (Leftrightarrow) (Asubset B)
设 (Next_v=) (N_v) 中第一个点。
点染色
弦图的色数=团数（最大团大小）
例题：[HNOI2008]神奇的国度
int n,m,v[N],tot,pes[N],pos[N],l[N],t[N];
bitset<N>ed[N];
bool vst[N];
vector<int>e[N];
struct node {
int l,id;
bool operator < (const node &y) const {return l<y.l;}
};
void mcs() {
memset(vst,0,sizeof(vst));
priority_queue<node>q;
per(i,n,1) ed[i][i]=1, q.push((node){0,i});
tot=n;
while(!q.empty()) {
int u=q.top().id; q.pop();
if(!vst[u]) {
pos[u]=tot, pes[tot--]=u, vst[u]=1;
for(auto v:e[u]) if(!vst[v]) q.push((node){++l[v],v});
}
}
}
int max_cliq(int ret=0) {
per(u,n,1) {
int cnt=0;
for(auto v:e[u]) if(pos[v]>pos[u]) cnt++;
ret=max(ret,cnt+1);
}
return ret;
}
int main() {
n=read(), m=read();
rep(i,1,m) {
int u=read(), v=read();
e[u].push_back(v), e[v].push_back(u);
ed[u][v]=ed[v][u]=1;
}
mcs();
printf("%d
",max_cliq());
return 0;
}
最大独立集
完美消除序列从前往后能选就选
最小团覆盖
弦图的最小团覆盖=最大独立集
区间图
两个点右边当且仅当两个区间交集非空
区间图一定是弦图
区间图的完美消除序列是按照右端点从小到大排序
选择最多区间使得区间不重 $ o $ 区间图最大独立集
#define l(x) a[i].second
#define r(x) a[i].first
int n,ans;
pii a[N];
int main() {
n=read();
rep(i,1,n) l(i)=read(), r(i)=read();
sort(a+1,a+n+1);
int mxr=0;
rep(i,1,n) if(mxr<l(i)) ans++, mxr=r(i);
printf("%d
",ans);
return 0;
}