Проверка графа на двудольность

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
 
using namespace std;
 
vector<int> parent, rank_;
 
int find(int u) {
    if (u != parent[u])
        parent[u] = find(parent[u]);
    return parent[u];
}
 
void union_sets(int u, int v) {
    u = find(u);
    v = find(v);
    if (u != v) {
        if (rank_[u] < rank_[v])
            swap(u, v);
        parent[v] = u;
        if (rank_[u] == rank_[v])
            rank_[u]++;
    }
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    parent.resize(n + 1);
    rank_.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        parent[i] = i;
 
    vector<int> color(n + 1, -1);
    bool is_bipartite = true;
 
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
 
        if (find(u) == find(v)) {
            if (color[u] == color[v]) {
                is_bipartite = false;
            }
        } else {
            union_sets(u, v);
            if (color[u] == -1 && color[v] == -1) {
                color[u] = 0;
                color[v] = 1;
            } else if (color[u] == -1) {
                color[u] = 1 - color[v];
            } else if (color[v] == -1) {
                color[v] = 1 - color[u];
            } else if (color[u] == color[v]) {
                is_bipartite = false;
            }
        }
 
        cout << is_bipartite;
    }
 
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <utility>
 
int main(){
   unsigned vertices, edges;
   std::cin >> vertices >> edges;
   
   // группы вершин двудольного графа
   std::vector<bool> red_group(vertices+1, false), blue_group(vertices+1, false);
   std::vector<bool> result(edges, false);
  
   enum State {Free, Red, Blue};
   
   for(unsigned i = 0, v, w; i != edges; ++i){
      std::cin >> v >> w;
      
      State state_v = blue_group[v] ? Blue : red_group[v] ? Red : Free ;
      State state_w = blue_group[w] ? Blue : red_group[w] ? Red : Free ;
      if ( (state_v == Blue && state_w == Blue) || 
           (state_v == Red  && state_w == Red) )
         break;
 
      if (state_v == Blue)
         std::swap(v, w);
      red_group[v] = true; blue_group[w] = true;
      
      result[i] = true;
   }
   for(unsigned i = 0; i != edges; ++i)
      std::cout << result[i];
   std::cout << std::endl;
}

#include <cassert>
#include <vector>
#include <iostream>
 
class Graph
{
public:
 
  Graph(unsigned n) : v(n)
  {
    for (unsigned i_v = 0; i_v < v.size(); ++i_v)
      v[i_v] = { i_v };
  }
 
  bool merge(unsigned i_a, unsigned i_b)
  {
    Id id_a = identify(i_a), id_b = identify(i_b);
 
    if (id_a.i_root == id_b.i_root)
      return id_a.half != id_b.half;
 
    if (id_a.half == id_b.half)
      v[id_a.i_root].flip ^= 1;
 
    v[id_a.i_root].flip ^= v[id_b.i_root].flip;
    v[id_a.i_root].i_parent = id_b.i_root;
 
    return true;
  }
 
private:
 
  struct Vertex
  {
    unsigned i_parent;
    unsigned char half, flip;
  };
 
  std::vector<Vertex> v;
 
  struct Id
  {
    unsigned i_root;
    unsigned char half;
  };
 
  Id identify(unsigned i_v)
  {
    assert(i_v < v.size());
 
    Id id = { i_v, v[i_v].half };
 
    for (unsigned i_parent; (i_parent = v[i_v].i_parent) != i_v; i_v = i_parent)
    {
      assert(i_parent < v.size());
 
      unsigned i_parent_parent = v[i_parent].i_parent;
      if (i_parent_parent != i_parent)
      {
        v[i_v].flip ^= v[i_parent].flip;
        i_parent = v[i_v].i_parent = i_parent_parent;
      }
 
      id.half ^= v[i_v].flip;
    }
 
    id.half ^= v[i_v].flip;
    id.i_root = i_v;
    assert(v[id.i_root].i_parent == id.i_root);
 
    return id;
  }
};
 
int main()
{
  unsigned n = 0, m = 0;
  std::cin >> n >> m;
  assert(n > 0 && m > 0);
 
  Graph g(n);
 
  for (; m > 0; --m)
  {
    unsigned a = 0, b = 0;
    std::cin >> a >> b;
    assert(a > 0 && b > 0);
    if (!g.merge(a - 1, b - 1))
      break;
 
    std::cout << "1";
  }
 
  for (; m > 0; --m)
    std::cout << "0";
 
  std::cout << std::endl;
}