F. Strange Housing CF694 贪心
题目大意：
给你一张图，选择一部分点进行染色，要求：
- 如果一条边的两个点都没有被选，那么这条边删除
- 染色的这些点两辆不想连
- 最后必须是一个大小为 (n) 的连通图
是否存在一种方案，存在输出 (YES) ，不存在输出 (NO)
题解：
任意选一个点作为起点，直接贪心即可。
- 如果这个点存在一个相邻的点被染色了，则不选这个点
- 如果这个点所有相邻的点都没有染色，则选择这个点
这样如果最后是一个大小为 (n) 的连通图，那么就输出 (YES)
如果最后不是，那么输出 (NO)
推断：最后不是连通图，那么一定不存在一种染色方案
证明：如果存在一个点不在这个连通块中，那么说明这个点所有相连的点都不在这个连通图，那么这个点就满足条件2，这个点应该要被选中。
感觉这个题目够不上当F题，放到F是在考验我的心理素质吗。。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
vector<int>G[maxn];
int ans[maxn];
bool vis[maxn];
queue<int>que;
void bfs(int x) {
while (!que.empty()) que.pop();
que.push(x);
while (!que.empty()) {
int u = que.front();
que.pop();
if (vis[u]) continue;
vis[u] = true;
bool flag = true;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (ans[v] == 1) flag = false;
que.push(v);
}
ans[u] = flag;
}
}
vector<int>res;
int main(){
int T;scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) G[i].clear(),ans[i] = -1,vis[i] = false;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
bfs(1);
bool flag = true;
res.clear();
for(int i=1;i<=n;i++){
if(ans[i]==-1) flag = false;
if(ans[i]==1) res.push_back(i);
}
if(flag) {
printf("YES
");
printf("%d
",res.size());
for(auto x:res) printf("%d ",x);
printf("
");
}
else printf("NO
");
}
return 0;
}