[PA 2015] 人赢 / Mistrzostwa 题解

前言

没啥好说的简单题。

正文

题目就是让你输出一个无向图里面，每个点度数至少为

d

的最大的联通子图。

那直接说怎么做。

显然，在这个子图里面度数少于

d

的点肯定是不能被包括进去的，所以我们应该能自然而然地想到，需要在全图中把它们删掉。

删掉的过程也很简单，将每一个度数少于

d

的点

u

加入队列删邻居即可。需要注意的是，减完度数之后，假如邻居的度数少于

d

的话，也要加入队列。

做完了之后就可以判断是不是还有点没有加入过这个队列，假如所有点都进过队列的话就代表无解。

判完无解之后，我们就得到了很多个连通分量，遍历每一个连通分量，取当中最大的集合就好了。

Code

时间复杂度为

\Theta (n\log n)

，瓶颈在排序。

CPP

#include <bits/stdc++.h>
#ifdef LOCAL
	#include "debug.h"
#else
	#define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,m,t,cnt=0;
const int maxn=2e5+10;
const double eps=1e-6;
vector<int> e[maxn];
int deg[maxn],vis[maxn];

signed main(){
	cin.tie(nullptr)->sync_with_stdio(0);
	cin>>n>>m>>t;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		e[u].pb(v);e[v].pb(u);
		deg[u]++,deg[v]++;
	}
	bitset<maxn> in;in.flip();
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(deg[i]<t) q.push(i),in[i]=0;
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v:e[u]){
			if(in[v]){
				deg[v]--;
				if(deg[v]<t){
					in[v]=0;
					q.push(v);
				}
			}
		}
	}
	bool flag=0;
	for(int i=1;i<=n;i++) if(in[i]){flag=1;break;}
	if(!flag) return cout<<"NIE"<<endl,0;
	vector<int> ans;
	for(int i=1;i<=n;i++){
		if(in[i] && !vis[i]){
			vector<int> res;
			queue<int> q;
			q.push(i);vis[i]=1;
			while(!q.empty()){
				int u=q.front();q.pop();res.pb(u);
				for(int v:e[u]){
					if(in[v] && !vis[v]){
						vis[v]=1,q.push(v);
					}
				}
			}
			if(res.size()>ans.size()) ans=res;
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for(int x:ans) cout<<x<<" ";
	return 0;
}

[PA 2015] 人赢 / Mistrzostwa 题解

文章操作

前言

正文

Code

相关推荐

评论

[PA 2015] 人赢 / Mistrzostwa 题解