整理的算法模板合集： ACM模板

---

cdq的论文

弦图

对于弦图：最大团 = 最小染色

子图：点集和边集都是原图的子集的图

诱导子图：是子图，不含其它边

团：子图，并且是完全图

极大团：不是任何一个团的子图

最大团：点数最多的团

最小染色：用最少的颜色染给每个点，使相邻点不同色

最大独立集：不相邻的最大点集

最小团覆盖：最少的团覆盖所有点

显然的结论：团数≤色数，最大独立集≤最小团覆盖

弦：连接环内两个不相邻的点的边

弦图：任意大于三的环都至少有一条弦

结论1：弦图的诱导子图是弦图

单纯点：设N(v)为v相邻的点集，v为单纯点当且仅当v+N(v)的诱导子图为团

结论2:任何一个弦图至少一个单纯点，不是完全图的弦图至少两个

完美消除序列

每个点正好出现一次的序列v1,v2,…,vn，满足vi在vi,vi+1,…,vn的诱导子图中为单纯点

结论3：一个无向图为弦图当且仅当它有一个完美消除序列

结论4：团数=色数，最大独立集=最小团覆盖

定理：一个无向图是弦图当且仅当它有一个完美消除序列。

用最大势算法$(MaximumCardinalitySearch)$可以在$O(n+m)$内求出一个消除序列的反序。只要倒过来就可以了。

for (int i=n,now;i;--i) { bool fg=0; while (!fg) { for (int j=v[best].size()-1;j>=0;--j) if (!vis[v[best][j]]) {fg=1;now=v[best][j];break;} else v[best].pop_back(); if (!fg) --best; } seq[i]=now;rk[now]=i;vis[now]=1; for (int e=head[now];e;e=nxt[e]) if (!vis[to[e]]) { v[++label[to[e]]].push_back(to[e]); best=max(best,label[to[e]]); } }

1 弦图的判定

朴素算法$O(nm)=O(n^3)$ 优化算法：设$\{vi+1...vn\}$中所有与vi相邻的点依次为$v_{j_1}...v_{j_k}$。 只需判断vj1是否与vj2…vjk相邻即可。 时间复杂度: $O(n+m)=O(n^2)$

for (int i=1;i<=n;++i) { top=0; for (int e=head[seq[i]];e;e=nxt[e]) if (rk[to[e]]<i) s[++top]=to[e]; for (int j=2;j<=top;++j) if (!g[s[1]][s[j]]) ans=0; }

最小色数问题 等于最小团数，也就是$ma{x}_{i=1}^{n}label[i]+1$

最大独立集 等于最小团覆盖数。按照完美消除序列一个个贪心选取即可。

2 弦图的最小染色问题

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在. 所谓N边关系,是指N个人 A1A2…An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

最多只有三角关系，很明显就是一个弦图（弦图就是任意大于三的环都至少有一个弦这样就不会构成四边、五边关系）将弦图分成多组的问题可以看做给弦图上的点染色且两个有直接边相连的点不能同色，这样就转化成了弦图的最小染色问题。直接跑优先队列优化的$O(nlogn+m)$的mcs算法即可。

int n,m,cnt=-1; const int MAX=2000015; int head[MAX]; bool vis[MAX],used[MAX]; int seq[MAX],label[MAX],color[MAX]; struct edge{ int nxt; int to; }e[MAX]; void add(int u,int v){ e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } typedef pair<int,int>p; priority_queue<p>q; void mcs(){ for(rg int i=1;i<=n;++i) q.push(p(0,i)); for(rg int i=n;i>=1;--i){ while(vis[q.top().second]) q.pop(); int u=q.top().second; q.pop(); seq[i]=u; vis[u]=1; for(rg int i=head[u];~i;i=e[i].nxt){ if(!vis[e[i].to]) q.push(p(++label[e[i].to],e[i].to)); } } } int solve(){ int res=0; for(rg int i=n;i>=1;--i){ memset(used,0,sizeof(used)); for(rg int j=head[seq[i]];~j;j=e[j].nxt){ used[color[e[j].to]]=1; } for(color[seq[i]]=1;used[color[seq[i]]];++color[seq[i]]); res=max(res,color[seq[i]]); } return res; } int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); for(rg int i=1;i<=m;++i){ int u=read(),v=read(); add(u,v); add(v,u); } mcs(); printf("%d\n",solve()); return 0; }

弦图小结

弦图总结