题解：AT_abc401_e [ABC401E] Reachable Set

思路

我们发现想要从顶点

1

出发，通过边能够到达的顶点集合恰好为

\{1,2,\ldots,k\}

必须满足集合中的点是连通的，所以用并查集维护，并记录每一个并查集里有多少个数，如果节点

1

所在的并查集里的数少于

i

个，就输出

-1

，否则就看

1

所在的并查集里数连向多少个不在集合里的点。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int n,m,b[200010],d[200010],e[200010];
vector<int>a[200001];
set<int>c;
int cz(int x){
	if(b[x]==x){
		return x;
	}
	return b[x]=cz(b[x]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		b[i]=i,d[i]=1;
	}
	for(auto i:a[1]){
		e[i]=1;
		c.insert(i);
	}
	printf("%d\n",c.size());
	for(int i=2;i<=n;i++){
		for(auto j:a[i]){
			if(j<=i){
				int x=cz(i),y=cz(j);
				if(x!=y){
					b[x]=y;
					d[y]+=d[x];
				}
			}
			else{
				if(e[j]==0){
					e[j]=1;
					c.insert(j);
				}
			}
		}
		c.erase(i);
		if(d[cz(i)]==i){
			printf("%d\n",c.size());
		}
		else{
			printf("-1\n");
		}
	}
}

题解：AT_abc401_e [ABC401E] Reachable Set

文章操作

思路

代码

相关推荐

评论

题解：AT_abc401_e [ABC401E] Reachable Set