Submission #1671872

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

int n, m;

vector<vector<int>> adj;

const int MAXN = 100005;
int color[MAXN];

bool bipartite;

void dfs(int u, int c) {
    color[u] = c;

    for (auto v : adj[u]) {
        if (color[v] == -1) {
            dfs(v, 1-c);
        }
        else if (color[v] == color[u]) {
            bipartite = false;
        }
    }
}

int main() {
    GI(n);
    GI(m);

    adj.resize(n+1);

    FORN(i, m) {
        int a, b;
        GI(a);
        GI(b);

        adj[a].PB(b);
        adj[b].PB(a);
    }

    memset(color, -1, sizeof color);

    bipartite = true;
    dfs(1, 0);

    if (!bipartite) {
        printf("%lld\n", 1LL*n*(n-1)/2 - m);
    }
    else {
        int cnt0 = 0;
        int cnt1 = 0;

        FOR1(i, n) {
            if (color[i] == 0) cnt0++;
            else cnt1++;
        }

        printf("%lld\n", 1LL*cnt0*cnt1 - m);
    }

    return 0;
}

Submission Info

Judge Result