Submission #3015916

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll n, m, a, b, color[100100];
vector<ll> G[100100];
bool nibu = true;

bool dfs(ll x, ll c){
    color[x] = c;
    for (ll i = 0; i < G[x].size(); i++){
        if (color[G[x][i]] == c) return false;
        if (color[G[x][i]] == 0 && !dfs(G[x][i], -c)) return false;
    }
    return true;
}

int main(void){
    // Your code here!
    cin >> n >> m;
    for (ll i = 0; i < m; i++){
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if (dfs(1, 1)){
        ll katahou = 0;
        for (ll i = 1; i <= n; i++){
            if (color[i] == 1) katahou++;
        }
        cout << katahou * (n - katahou) - m << endl;
    } else {
        cout << n * (n - 1) / 2 - m << endl;
    }
}

Submission Info

Judge Result