题目大意：一共有n个人，每天早上会有两个人成为朋友，朋友关系不具有传递性，晚上，它们会组织旅游，如果一个人去旅游，那么他不少于$k$个朋友也要和他去旅游，求每天的最大旅游人数
一开始并没有想到反向建图，并查集搞了好久也没出解，看了题解的思路，大概是这样的
转化问题，反向建图，把正序往图里建边换成每次倒序在图里删边。
显然，一开始/删掉边之后，度小于K的点一定不可用，那么把它删掉，和它相连的边也删掉
那么可能这个点删掉以后，和它相连的某个点度也小于K了，再把那个点也删掉...发现这是一个类似于拓扑的过程
由于每个点只会被删掉1次，所以复杂度大约是$O(n+m)$
边全都加完的图中，也可能有些点既没有入度也没有出度，答案里要把它们去掉
1 #include <set> 2 #include <queue> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #define N 200100 7 #define ll long long 8 using namespace std; 9 //re 10 int gint() 11 { 12 int ret=0,fh=1;char c=getchar(); 13 while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();} 14 while(c>='0'&c<='9'){ret=ret*10+c-'0';c=getchar();} 15 return ret*fh; 16 } 17 int n,m,K,ma,cte,sum; 18 int head[N],inc[N],ans[N]; 19 struct Edge{int to,nxt,val;}edge[N*2]; 20 void ae(int u,int v){ 21 cte++;edge[cte].to=v,inc[v]++; 22 edge[cte].nxt=head[u],head[u]=cte;} 23 queue<int>que; 24 void Pop(int x) 25 { 26 que.push(x); 27 while(!que.empty()) 28 { 29 int x=que.front();que.pop(); 30 if(head[x]!=0) sum--; 31 for(int j=head[x];j;j=edge[j].nxt){ 32 if(edge[j].val==-1)continue; 33 edge[j].val=edge[j^1].val=-1; 34 int v=edge[j].to; 35 inc[v]--; 36 if(inc[v]<K) que.push(v); 37 }head[x]=0; 38 } 39 } 40 41 int main() 42 { 43 scanf("%d%d%d",&n,&m,&K); 44 int x,y,z;cte=1;sum=n; 45 for(int i=1;i<=m;i++) 46 x=gint(),y=gint(),ae(x,y),ae(y,x); 47 for(int i=1;i<=n;i++) 48 if(head[i]==0) sum--; 49 for(int i=1;i<=n;i++) 50 if(inc[i]<K) Pop(i); 51 for(int j=m;j>=1;j--) 52 { 53 ans[j]=sum; 54 if(edge[j<<1].val==-1) 55 {continue;} 56 x=edge[j<<1].to; 57 y=edge[j<<1|1].to; 58 inc[x]--,inc[y]--; 59 edge[j<<1].val=edge[j<<1|1].val=-1; 60 if(inc[x]<K) Pop(x); 61 if(inc[y]<K) Pop(y); 62 } 63 for(int j=1;j<=m;j++) 64 printf("%d ",ans[j]); 65 return 0; 66 }