圖論：弦圖最小點染色

弦圖的定義：當圖中任意長度大于3的環都至少有一個弦時，?一個無向圖稱為弦圖

不存在四角、五角等關系就說明這個圖是一個弦圖

題目問的是，任何一對相互認識的人不可以組一隊，問最多可以組多少對

所有的人構成的關系圖是一個弦圖（長度超過 3 的環中必有一條弦），求出它的完美性消除序列，根據完美消除序列逆序貪心的染色，最終所用的色數就是本題的答案

好難啊

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,ans;
int head[10005],d[10005],q[10005],col[10005],hash[10005];
bool vis[10005];
struct data{int to,next;}e[2000005];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        ins(u,v);ins(v,u);
    }
    for(int i=n;i;i--)
    {
        int t=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&d[j]>=d[t])t=j;
        }
        vis[t]=1;q[i]=t;
        for(int j=head[t];j;j=e[j].next)
            d[e[j].to]++;
    }
    for(int i=n;i>0;i--)
    {
        int t=q[i];  
        for(int j=head[t];j;j=e[j].next)hash[col[e[j].to]]=i;
        int j;
        for(j=1;;j++)if(hash[j]!=i)break;
        col[t]=j;
        if(j>ans)ans=j;
    }
    printf("%d",ans);
    return 0;
}

?再補上一些區間圖的定義和應用

給定一些區間，定義一個相交圖為每個頂點表示一個區間，兩個點有邊當且僅當兩個區間的交集非空。

一個圖為區間圖當它是若干個區間的相交圖

區間圖一定是弦圖

應用有

1.給定n個區間，要求選擇最多的區間使得區間不互相重疊。區間圖的最大獨立集。2.有n個積木，高度均為1，第i個積木的寬度范圍為[Li, Ri]，選擇一個積木的下落順序使得最后積木總高度盡可能小。把一層積木看成一個顏色，轉化為區間圖的色數問題。

好像解法依賴于一個極其復雜的數據結構？