Strange Housing CodeForces - 1471F

题意：

有 n 个点和 m 条边，对点进行染色。要求一条边的两个点不能都染色，并且删除两端都没有染色的边之后，图连通。请给出一种染色方案。

题解：

第一反应就是01染色，但是题目是有可能存在奇环的，那怎么办？
01染色是保证1和1,0和0都不能相邻，如果把1当做染色，根据本题，0是可以相邻的，那我们把01染色的dfs改成bfs的形式，也就是与1相邻的点都是0，然后对于每个0，所能到的下一个点就是1，然后对1操作，1的周围都是0，这样循环进行就可以
BFS遍历所有的点。

1. 如果当前节点没有染色，且相邻的所有节点没有染色，就染色，否则不染色。
2. 如果当前节点已经染色，那么把相邻的所有节点标记不染色。
   证明：显然这种方案不会存在一条边的两端都染色的情况，并且如果图不连通，一定是有一个点连接的所有点都不染色，而这样的点一定会在第一种情况下被染色，所以图一定是连通的。
   当然如果图本身就不连通直接输出NO
   u1s1，div2的F题比我想象的要简单多

   代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define LL long long
#define eps (1e-8)
const int maxn = 3e5 + 10;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
struct node
{
    int v, nxt;
}e[maxn << 1];
int head[maxn], cnt;
void add(int u, int v)
{
    e[++cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
int vis[maxn];//标记为1是染色，0位不染色，-1位还未遍历的点 
queue<int>q;
void bfs(int u)
{
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;// 
        if (vis[v] == -1)
        {
            vis[v] = 0; 
            q.push(v);//存的都是不染色的点
        }
    }
}
void solve()
{
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;//v为染色点 
            if (vis[v] == -1)
            {
                bfs(v);
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        cnt = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; i++)
        {
            head[i] = 0;
            vis[i] = -1;
        }
        int u, v;
        while (m--)
        {
            scanf("%d%d", &u, &v);
            add(u, v), add(v, u);
        }
        bfs(1);
        solve();
        int flag = 1, ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] == 1)ans++;
            else if (vis[i] == -1)//说明有的点没有遍历到，图不连通 
            {
                flag = 0;
            }
        }
        if (flag)
        {
            printf("YES\n");
            printf("%d\n", ans);
            for (int i = 1; i <= n; i++)
            {
                if (vis[i] == 1)printf("%d ", i);
            }
            printf("\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}