本文移植自个人的原博客（原文）

论文

弦图与区间图-陈丹琦

定义

团

图$G$的一个子图$G’=(V’,E’)$，$G’$为关于$V’$的完全图。

极大团

一个团是极大团当它不是其它团的子集。

最大团

点数最多的团。

弦

连接环中不相邻的两个点的边。

弦图

一个无向图称为弦图当且仅当图中任意长度大于$3$的环都至少有一个弦。

单纯点

设$N(v)$表示与点$v$相邻的点集。一个点称为单纯点当$\lbrace v \rbrace + N(v)$的诱导子图为一个团。

完美消除序列

这是一个序列$v_i$，它满足$v_i$在$v_i,…,v_n$的诱导子图中为单纯点。

弦图的判定

存在完美消除序列的图为弦图。

最小色数

用最少的颜色给点染色使相邻点颜色不同，$χ(G)$为其色数。

最大独立集

最大的一个点集使任意两个点不相邻，$α(G)$为其点数。

最小团覆盖

用最少个数的团覆盖所有的点，$κ(G)$为其团数。

求解

完美消除序列

可通过最大势算法求解完美消除序列，维护每个点的势（初始化为零），每次将势最大的点从图中删除，并加入到完美消除序列中，然后将所有与其相连的点的势加一，直到图为空为止。时间复杂度为$O(n^2+m)$,可以用桶优化到$O(n+m)$（并不会）（但是可以用堆优化）。

最小色数的求解

简单的贪心策略，遍历完美消除队列，将当前点染为可行的最小编号颜色，最大的编号即为答案。

最大独立集的求解

仍然是贪心，遍历完美消除队列，如果当前点的所有相邻的点不在独立集中，则将该点加入独立集。

最小团覆盖的求解

最小团覆盖数=最大独立集数

（以上一切都不会证）

HNOI2008 神奇的国度

题目描述

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

输入输出格式

输入格式

第一行两个整数$N，M$。表示有$N$个人，$M$对认识关系. 接下来$M$行每行输入一对认识关系。

$1<=N<=10000,1<=M<=1000000$

输出格式

输出一个整数，最少可以分多少队。

样例

输入样例

输出样例

3
(1,3)(2)(4)为一种可行方案

题解

根据题目所给条件可知，任何点数大于三的环都存在弦，可知该图为弦图，直接求解最小染色数即可。（该题数据范围较小，不需要桶优化）

#include<iostream>
#include<cstdio>
using namespace std;
const int N =1e5+1;
const int inf = 0x7fffffff;
struct nd{int ne,to;}e[20*N];
int head[N],cnt,tot,vis[N],p[N],q[N],n,m,ans,c[N];
bool use[N];
void in(int x,int y)
{
    e[++cnt].ne=head[x];
    e[cnt].to=y;
    head[x]=cnt;
    return;
}
int main()
{
//    freopen("bzoj_1006.in","r",stdin);
//    freopen("bzoj_1006.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;++i)scanf("%d%d",&x,&y),in(x,y),in(y,x);
    int x=1;
    while(tot!=n)
    {
        for(int i=1;i<=n;++i)if(p[i]>p[x]&&!vis[i])x=i;
        vis[x]=1;q[++tot]=x;
        for(int i=head[x];i;i=e[i].ne)p[e[i].to]++;
        x=inf;
    }
    for(int t=1;t<=n;++t)
    {
        int x=q[t];
        for(int i=1;i<=ans;++i)use[i]=0;
        for(int i=head[x];i;i=e[i].ne)use[c[e[i].to]]=true;
        int now=1;
        while(use[now])now++;
        c[x]=now;
        if(now>ans)ans=now;
    }
    printf("%d",ans);
}