题解 P3852 【[TJOI2007]小朋友】

· · 题解

弦图 完美消除序列

弦图的前置知识

诱导子图：子图中任意一条边的两个端点一定也都在这个子图中

最大团：团中任意两点之间一定都有边，而包含顶点最多的团就是最大团

最小团覆盖：用最少的团覆盖图中所有的点

最大独立集：独立集中任意两点之间一定都没有边，而包含顶点最多的独立集就是最大独立集

最小染色：用最少的颜色给图染色使得图中任意相邻的两点颜色不相同

弦图：无向图中任意长度大于3的环都至少有一个弦，所谓弦就是连接环中不相邻两点的边

一般来讲：

①最大团数<=最小染色数

②最大独立集<=最小团覆盖

对于弦图来讲：

①最大团数==最小染色数

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

单纯点：如果与顶点V相邻的所有点能构成一个团，那么V就是个单纯点

③任何一个弦图都有至少一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点

完美消除序列：一个点的序列（每个点刚好出现1次）v_1, v_2,…,v_n满足v_i在诱导子图{v_i, v_{i+1},…,v_n}中为一个单纯点

一个无向图是弦图的充要条件是存在完美消除序列

再看本题的题意，题目中的数据保证M对矛盾所构成的图中不会有超过3个点的环

显然符合弦图的定义嘛

而题目中要求的矛盾关系，就是不能选择相邻的两个点嘛

妥妥的弦图最大独立集

做法

对于这种题目，我们只需要求个完美消除序列就好了，然后在完美消除序列上从前往后贪心取点即可

对于完美消除序列的求取方法

从后往前确定序列的点，每取一个点都把还没加入序列的和它相连的点的标号+1，每次取点选择标号最大的点之一，这样我们便可以求出一个完美消除序列

复杂度 O(m+n)

接下去在完美消除序列上跑个贪心就好了

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();}
    return flag?-x:x;
}
const int N=1e5+5;
int n,m,vis[N],seq[N],num[N],id=1,ans;
int to[N],nxt[N],head[N],cnt;
vector<int>cg[N];
void add(int u,int cg){to[++cnt]=cg;nxt[cnt]=head[u];head[u]=cnt;}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i) cg[0].push_back(i);
    for(int i=1;i<=n;++i)
    {
        int fg=0,now;
        while(!fg)
        {
            for(int j=cg[id].size()-1;j>=0;--j)
            if (!vis[cg[id][j]]) {fg=1;now=cg[id][j];break;}
            else cg[id].pop_back();
            if(!fg) --id;
        }
        seq[i]=now;vis[now]=1;
        for (int e=head[now];e;e=nxt[e])
        if (!vis[to[e]])
        {
            cg[++num[to[e]]].push_back(to[e]);
            id=max(id,num[to[e]]);
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=n;i;--i) if(!vis[seq[i]])
    {
        ++ans;vis[seq[i]]=1;
        for(int e=head[seq[i]];e;e=nxt[e]) vis[to[e]]=1;
    }
    printf("%d\n",ans);
}