本文主要是介绍Trips CodeForces - 1037E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://codeforces.com/contest/1037/problem/E
逆向考虑 先拓扑把度数小于k的点入队列松驰其他点 最后剩下的点的数量就是最后一次查询的答案
然后逆向枚举删边 还是拓扑 把度数小于k的点入队列 删完当前这条边后 有几个点度数变为小于k 答案就减几
注意无向图拓扑时边要特判
#include <bits/stdc++.h>
using namespace std;struct node1
{int u;int v;
};struct node2
{int id;int v;int next;
};queue <int> que;
node1 pre[200010];
node2 edge[400010];
int first[200010],degree[200010],book[200010],ans[200010],flag[200010];
int n,m,k,num;void addedge(int id,int u,int v)
{edge[num].id=id;edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void init()
{int i,id,u,v;for(i=1;i<=n;i++){if(degree[i]<k){que.push(i);book[i]=1;}}while(!que.empty()){u=que.front();que.pop();for(i=first[u];i!=-1;i=edge[i].next){id=edge[i].id,v=edge[i].v;if(flag[id]==0){degree[v]--;if(degree[v]<k&&book[v]==0){que.push(v);book[v]=1;}flag[id]=1;}}}for(i=1;i<=n;i++) if(book[i]==0) ans[m]++;
}void solve()
{int i,j,id,u,v;for(i=m;i>=1;i--){ans[i-1]=ans[i];if(flag[i]) continue;flag[i]=1;degree[pre[i].u]--,degree[pre[i].v]--;if(degree[pre[i].u]<k&&book[pre[i].u]==0){que.push(pre[i].u);book[pre[i].u]=1;ans[i-1]--;}if(degree[pre[i].v]<k&&book[pre[i].v]==0){que.push(pre[i].v);book[pre[i].v]=1;ans[i-1]--;}while(!que.empty()){u=que.front();que.pop();for(j=first[u];j!=-1;j=edge[j].next){id=edge[j].id,v=edge[j].v;if(flag[id]==0){degree[v]--;if(degree[v]<k&&book[v]==0){que.push(v);book[v]=1;ans[i-1]--;}flag[id]=1;}}}}for(i=1;i<=m;i++) printf("%d\n",ans[i]);
}int main()
{int i;scanf("%d%d%d",&n,&m,&k);memset(first,-1,sizeof(first));num=0;for(i=1;i<=m;i++){scanf("%d%d",&pre[i].u,&pre[i].v);addedge(i,pre[i].u,pre[i].v);addedge(i,pre[i].v,pre[i].u);degree[pre[i].u]++,degree[pre[i].v]++;}init();solve();return 0;
}
这篇关于Trips CodeForces - 1037E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
