题目大意

给出一个 $n$ 个点 $n$ 条边的无向图，需要找出 $k$ 个点，并且其中任意两点之间没有边直接相连。

题目思路

二分图板题，把所有点黑白染色，然后选出两种颜色中数量更多的点，最后注意一下图可能不连通即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,o1,o2,c[114514],tot,ch[114514],tt;
queue<int>q;
vector<int>v[114514],v1,v2,ans;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		o1=read();o2=read();
		v[o1].push_back(o2);
		v[o2].push_back(o1);
	}
	k=read();
	for(int g=1;g<=n;g++){
		if(c[g])continue;
		c[g]=1;q.push(g);
		o1=1;o2=0;
		v1.clear();v2.clear();
		v1.push_back(g);
		for(;!q.empty();){
			int p=q.front();q.pop();
			for(int i=0;i<v[p].size();i++){
				if(c[v[p][i]]==c[p])break;
				if(!c[v[p][i]]){
					if(c[p]==1)o2++,v2.push_back(v[p][i]);
					else o1++,v1.push_back(v[p][i]);
					c[v[p][i]]=3-c[p];
					q.push(v[p][i]);
				}
			}
		}
		if(o1>=o2)for(int i=0;i<v1.size();i++)ans.push_back(v1[i]);
		else for(int i=0;i<v2.size();i++)ans.push_back(v2[i]);
	}
	if(ans.size()<k)cout<<0;
	else for(int i=0;i<k;i++)cout<<ans[i]<<' ';
	return 0;
}