проверка на двудольность

#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <map>
#include <cmath>

#define se second
#define fi first
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

vector<vector<int>> g;
vector<bool> used;
vector<int> col;
vector<int> answ;

bool dfs(int h, int next_col) {
    used[h] = true;
    col[h] = next_col;
    if (next_col == 0) answ.push_back(h + 1);
    for (auto e : g[h]) {
        if (col[e] == next_col) return false;
        if (!used[e]) dfs(e, next_col ^ 1);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    //vector<vector<int>> g(n, vector<int>(n, 0)); если бы объявляли локально
    g.assign(n, vector<int>(n, 0));
    used.assign(n, false);
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    col.assign(n, -1);
    dfs(0, 0);
    cout << (int)answ.size() << '\n';
    for (auto e : answ) cout << e << ' ';
    return 0;
}