题目描述
刚入学，班上一共有 n 名同学，互相都不认识。每天，班上会多出一对新朋友(xi,yi),xi≠yi(xi,yi),xi≠yi，在这对新朋友确定后，大家会一起商量翘课的事情。一个人翘课，仅当他的至少 K 个朋友也翘课。问每天最多会有多少人翘课。
题解（暴力部分）：
感觉还挺具有思考性的，蒟蒻考场困得一批暴力都没打对，故写文以记之。
- 对于$k==1$的分，显然只需要记录一下每一个点有没有边连着即可，搞一个$v[i]$记录i这个节点有没有被连边，每加一个边判一下即可。
部分代码：1
2
3
4
5
6for (int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
if (!v[x]) v[x]=1,ans++;
if (!v[y]) v[y]=1,ans++;
printf("%d\n",ans);
}
- 对于$k<=2$的分就是找图中的环，看有多少节点。本来想的是$tarjan$但无向图不会写，听说正解就是$dfs$跑一边即可。。不是很懂。。
题解（正解）：
对于$k<n,n<=2000$的分，由于是正解前置技能所以放在后面说明：
读入的时候记录每一个节点的度，考虑每一个度小于k的节点，他们肯定就是翘课不了的。（因为即使他们的所有朋友都能翘课，他的朋友总和小于k，所以还是翘不了）
既然这个点翘不了课，那对于与其连边的其他点来说，这个就没有贡献了，便可以把这条边删去。（易得）
然后重新判断删去所有无贡献节点后的新图，若又出现度小于k的节点，则重复这种操作即可。（传递性）
所以一开始没听到完整过程的我只知道类似拓扑排序删边，还是有点迷茫的。无向图跟拓扑排序有屁关系？？
每次加一条边我们就重新做一遍以上操作，计算新的答案，所以是$O(N^2)$。
考虑正解：
因为加边只会对之前的图有影响，所以可以离线（好像不算？）读入所有的边，算出最终的答案。
倒序地依次减边，若对于之前的图此边已经减去了，直接继承上一次的答案，不然就减完边再进行上述递归判断。复杂度$O($能过$)$。
核星代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void deal()
{
ans=0;
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++)
if (d[i]<k) v[i]=1,q.push(i);
//将度小于K的点入队
while (!q.empty())
{
int kk=q.front(); q.pop();
for (int i=fir[kk];i;i=e[i].next)
{
int u=e[i].u; d[u]--; e[i].del=1;
//删除连边的点的度，将边删除（打记号）
if (!v[u]&&d[u]<k) v[u]=1,q.push(u);
}
}
for (int i=1;i<=n;i++) if (!v[i]) ans++;
//计算答案。
}