Trips

题目链接

题目大意:

共有n（2e5）个人，刚开始都不认识，有m（2e5）天，第 i 天xi和yi认识了，认识不会传递，也就是a认识b，b认识c，a不一定认识c。这些人每天都想去旅游，如果每个人有他的k个朋友去旅游他才去。问每天最多去多少人。
分析一下。。
可以看成一个图，刚开始是空图，没有边，然后一次连接一个边，如果一个子图中的点要去那么在这个子图中的每个点，在这个子图中的度数都大于等于k。
就想到这里想不出来了。。
一种思想:
倒过来，就是先把所有边加上，然后找个答案就是m天的答案，然后依次删除边，再找答案。
怎么找答案呢？ 刚开始 度数小于k的人肯定不行，加到队列里，然后bfs让与它相连的点的度数减1，然后 如果这个点的度数小于k就继续。。
如果当前状态不行的点，因为是删除边，所以以后的状态都肯定不行了。

因为是删除边，如果用普通的前向星建图没办法删除，（遍历一遍？肯定不行） 所以可以用set存图。
代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int maxn = 2e5+5;
typedef long long ll;
set<int> ss[maxn];
int du[maxn];
int ans[maxn];
int x[maxn];
int y[maxn];
int sum = 0;
int vis[maxn];
queue<int> qq;
int k;

void bfs()
{
   
	while(!qq.empty())
	{
   
		int xx = qq.front();
		qq.pop();
		set<int> :: iterator it = ss[xx].begin();
		for (;it != ss[xx].end(); it ++ )
		{
   
			int v = *it;
			if(vis[v])
				continue;
			du[v] -- ;
			if(du[v] < k)
			{
   
				qq.push(v);
				vis[v] = 1;
				sum -- ;
			}
		}
	}
}

int main()
{
   
	int n,m;
	scanf("%d%d%d",&n,&m,&k);
	for (int i= 1; i<= m; i ++ )
	{
   
		scanf("%d%d",&x[i],&y[i]);
		du[x[i]] ++ ;
		du[y[i]] ++ ;
		ss[x[i]].insert(y[i]);
		ss[y[i]].insert(x[i]);
	}
	sum = n;
	for (int i = 1; i <= n; i ++ )
	{
   
		if(du[i] < k)
		{
   
			sum -- ;
			qq.push(i);
			vis[i] = 1;
		}
	}
	bfs();
	ans[m] = sum;
	for(int i=  m; i > 1; i -- )
	{
   
		
		int xx = x[i];
		int yy = y[i];
		if(vis[xx] == 0 && vis[yy] == 0)
		{
   
			ss[xx].erase(yy);
			ss[yy].erase(xx);
			du[xx] -- ;
			du[yy] -- ;
			if(du[xx] < k)
			{
   
				sum -- ;
				vis[xx] = 1;
				qq.push(xx);
			}
			if(du[yy] < k)
			{
   
				sum -- ;
				vis[yy] = 1;
				qq.push(yy);
			}
			bfs();
		}
		ans[i - 1] = sum;
	}
	for (int i= 1; i <= m; i ++ )
	{
   
		printf("%d\n",ans[i]);
	}
	// printf("\n");
}