题解 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); } ```