这是本文档旧的修订版！

2020牛客国庆集训派对

Day 1

I、Saba1000kg

题意

给定一张图，$q$ 个询问，每次询问只考虑图中 $s_i$ 个点构成的连通块数。数据保证 $\sum s_i\le 10^5$。

题解

考虑分块。当 $s_i\lt k$ 时暴力 $O(s_i^2)$ 枚举所有点对同时维护并查集。 $s_i\ge k$ 时暴力 $O(m)$ 枚举所有边同时维护并查集。

从均摊复杂度考虑，消耗每点 $\sum s_i$ 的复杂度为 $O(\max(\cfrac {s_i^2}{s_i}(s_i\lt k),\cfrac m{s_i}(s_i\ge k))\log s_i)=O(\max (k,\cfrac mk)\log k)$。

取 $k=O(\sqrt m)$ 时总时间复杂度为 $O(\sum s_i\sqrt m\log m)$。

查看代码

const int MAXN=1e5+5;
set<int>g[MAXN];
struct Edge{
	int u,v;
}edge[MAXN];
int p[MAXN],b[MAXN];
bool vis[MAXN];
int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
void Merge(int x,int y){
	int xx=Find(x),yy=Find(y);
	if(xx!=yy)
	p[xx]=yy;
}
int main()
{
	int n=read_int(),m=read_int(),q=read_int(),limt=sqrt(m+10);
	_for(i,0,m){
		edge[i].u=read_int(),edge[i].v=read_int();
		g[edge[i].u].insert(edge[i].v);
		g[edge[i].v].insert(edge[i].u);
	}
	while(q--){
		int sz=read_int(),ans=0;
		_for(i,0,sz){
			b[i]=read_int();
			vis[b[i]]=true;
			p[b[i]]=b[i];
		}
		if(sz<limt){
			_for(i,0,sz)
			_for(j,i,sz){
				if(g[b[i]].count(b[j]))
				Merge(b[i],b[j]);
			}
		}
		else{
			_for(i,0,m){
				if(vis[edge[i].u]&&vis[edge[i].v])
				Merge(edge[i].u,edge[i].v);
			}
		}
		_for(i,0,sz){
			ans+=(Find(b[i])==b[i]);
			vis[b[i]]=false;
		}
		enter(ans);
	}
	return 0;
}

CVBB ACM Team

目录

2020牛客国庆集训派对

Day 1

I、Saba1000kg

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

2020牛客国庆集训派对

Day 1

I、Saba1000kg

题意

题解

页面工具