题意
一共有 \(n\) 个人，他们开始互不认识，而每天早上不认识的两个人会变成朋友。一共有 \(m\) 天，每天晚上有的人要去旅行，去旅行的人必须满足有至少 \(k\) 个朋友也去旅行。求每天去旅行的最大人数。
思路
-
读题后发现，想要判断一个人能否去旅行，就要知道他的朋友能否旅行。这是一个“套娃”的判断，如果直接考虑有多少人能去旅行较为困难。
-
因此，我们可以考虑有多少人不能去旅行。首先，那些朋友数量不足 \(k\) 个的肯定不行，将他删去。删去后我们发现，他的一些朋友此时朋友数量变小后不足 \(k\) 个，则将他们也删去，以此类推，就可以统计出一个固定的图中有多少人不能旅行，单次统计时间复杂度 \(O(n)\)。
-
接下来考虑加边。如果在每个时刻都进行一次上述操作，则总体时间复杂度为 \(O(nm)\)，会超时。但正难则反，我们可以变加边为删边，从最后一个时刻向前计算，每次删除图中的一条边。删边后，有些人朋友数量小于 \(k\)，则将他们删去，再考虑他们的朋友，以此类推。总体时间复杂度 \(O(n+m)\)。
-
实现时有一些细节，如一条边删去后要标记两条边被删去（因为是无向图），防止重复删边。还有只有在某个点的度数减小后恰好等于 \(k - 1\) 才能删去，防止重复删点。
代码
#include<bits/stdc++.h>
#define int long long
#define MAXN 400005
using namespace std;
int n,m,k,ans[MAXN],eu[MAXN],ev[MAXN],d[MAXN],sum;
int cnt,head[MAXN];
queue<int>q;
struct Edge{int value,next,w;
}adj[MAXN];
void addedge(int u,int v){adj[++cnt].value=v;adj[cnt].next=head[u];adj[cnt].w=1; //标记该边未被删除 head[u]=cnt;
}
void solve(){while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i;i=adj[i].next){if(adj[i].w==1){int y=adj[i].value;d[y]--;if(d[y]==k-1){ //新出现的不符合要求的点入队 q.push(y);sum--;}adj[i].w=0; adj[(i%2==0?i-1:i+1)].w=0;//标记该边已被删除 }}}
}
signed main(){scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=m;i++){scanf("%lld%lld",&eu[i],&ev[i]);addedge(eu[i],ev[i]);addedge(ev[i],eu[i]);d[eu[i]]++;d[ev[i]]++;}sum=n;for(int i=1;i<=n;i++){if(d[i]<k){ //本来度数不足k个的点入队 q.push(i);sum--;}}for(int i=m;i;i--){solve();ans[i]=sum;if(adj[i*2].w==1&&adj[i*2-1].w==1){//若该边还没有被删除 d[eu[i]]--;if(d[eu[i]]==k-1)q.push(eu[i]),sum--;//删边后若有点不符合要求则加入队列 d[ev[i]]--;if(d[ev[i]]==k-1)q.push(ev[i]),sum--;adj[i*2].w=0;adj[i*2-1].w=0;}}for(int i=1;i<=m;i++){printf("%lld\n",ans[i]);}return 0;
}