Submission #2237520

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct BipartiteGraph {
  int N;
  vector<vector<int>> G;
  vector<int> coler;
  BipartiteGraph() {}
  BipartiteGraph(int N) : N(N), G(N), coler(N) {}
  void add_edge(int s, int t) {
    G[s].emplace_back(t);
  }
  bool is_bipartite_graph() {
    for (int i = 0; i < N; i++) coler[i] = 0;
    for (int i = 0; i < N; i++) {
      if (coler[i]) continue;
      int c = 1;
      coler[i] = c;
      stack<int> S;
      S.emplace(i);
      while (!S.empty()) {
        int v = S.top(); S.pop();
        for (auto &u : G[v]) {
          if (coler[u] == coler[v]) return false;
          if (coler[u]) continue;
          coler[u] = -coler[v];
          S.emplace(u);
        }
      }
    }
    return true;
  }
  pii get_count() {
    if (!is_bipartite_graph()) return pii(-1, -1);
    int b = 0, w = 0;
    for (int i = 0; i < N; i++) b += coler[i] > 0, w += coler[i] < 0;
    return pii(b, w);
  }
};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N, M;
  cin >> N >> M;
  BipartiteGraph BG(N);
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    A--, B--;
    BG.add_edge(A, B);
    BG.add_edge(B, A);
  }
  pii p = BG.get_count();
  cout << (p != pii(-1, -1) ? (ll)p.first * p.second - M : (ll)N * (N - 1) / 2 - M) << endl;

  return 0;
}

Submission Info

Judge Result