这是个标准的弦图，但如果不知道弦图就惨了=_=
趁着这个机会了解了一下弦图，主要就是完美消除序列，求出了这个就可以根据序列进行贪心染色。
貌似这个序列很神，但是具体应用不了解……
这道题为什么可以这么做不理解……
我真是太弱了……
上代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#define N 100100
#define M 2000100
using namespace std;
struct sss
{
int num;
int du;
};
int n, m;
int p[N] = {}, next[M], v[M], bnum = ;
int du[N] = {}, vis[N] = {}, qu[N];
priority_queue<sss> q;
int hcolor[N] = {}, color[N] = {}, colornum = , huse[N] = {}; bool operator < (sss x, sss y)
{
return x.du < y.du;
} void addbian(int x, int y)
{
bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y;
bnum++; next[bnum] = p[y]; p[y] = bnum; v[bnum] = x;
} void make_queue()
{
for (int i = ; i <= n; ++i)
{
sss x; x.num = i; x.du = ;
q.push(x);
}
int dc = ;
while (dc < n)
{
sss y = q.top(); q.pop();
while (vis[y.num])
{
y = q.top();
q.pop();
}
vis[y.num] = ;
qu[++dc] = y.num;
int k = p[y.num]; sss ne;
while (k)
{
if (!vis[v[k]])
{
du[v[k]]++; ne.du = du[v[k]];
ne.num = v[k]; q.push(ne);
}
k = next[k];
}
}
} void color_dian()
{
for (int i = ; i <= n; ++i)
{
int x = qu[i];
int k = p[x];
int all = ;
while (k)
{
if (color[v[k]] != ) all = ;
huse[color[v[k]]] = x;
k = next[k];
}
int pd = ;
for (int i = ; i <= colornum; ++i)
if (huse[i] != x)
{
pd = ;
color[x] = i;
break;
}
if (!pd) color[x] = ++colornum;
}
printf("%d\n", colornum);
} int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i <= m; ++i)
{
int x, y; scanf("%d%d", &x, &y);
addbian(x, y);
}
make_queue();
color_dian();
return ;
}