题目：Trips
题意：有n个人，m天，每天晚上都有两个人成为朋友，当一个人的k个朋友都去旅游时这个人才能去旅游。问每天晚上最多能有多少人去旅游。
思路：
即求一个最大子图，使得每个节点的度大于等于k。
定义操作delete为在当前的图中删去所有度小于k的点。
先根据所有的边构图，在每次删去一些边，顺便处理即可。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 200000struct Pair {int x,y;Pair() {}Pair(int xx,int yy) {x=xx,y=yy;}bool operator < (const Pair& oth) const {return x<oth.x||(x==oth.x&&y<oth.y);}
};int n,m,k;
int a[maxn+5],b[maxn+5];
vector<int> g[maxn+5];
int del[maxn+5],d[maxn+5];void readin() {scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);a[i]=x,b[i]=y;g[x].push_back(y);g[y].push_back(x);d[x]++,d[y]++;}
}queue<int> que;
int cnt;
map<Pair,int> mp;void Delete(int x) {if(d[x]>=k||del[x]) return ;que.push(x);del[x]=true;cnt--;while(!que.empty()) {int h=que.front();que.pop();for(int i=0; i<g[h].size(); i++) {int y=g[h][i];if(del[y]) continue;if(mp.count(Pair(h,y))==0) d[y]--;if(d[y]<k) del[y]=true,cnt--,que.push(y);}}
}int ans[maxn+5];int main() {readin();cnt=n;for(int i=1; i<=n; i++) Delete(i);for(int i=m; i>=1; i--) {ans[i]=cnt;mp[Pair(a[i],b[i])]=true;mp[Pair(b[i],a[i])]=true;if(!del[b[i]]) d[a[i]]--;if(!del[a[i]]) d[b[i]]--;Delete(a[i]),Delete(b[i]);}for(int i=1; i<=m; i++) printf("%d\n",ans[i]);return 0;
}