Submission #2526088

---

Source Code Expand

#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define F             "TRIPEDGE"
#define READ          freopen(F".inp", "r", stdin)
#define WRITE         freopen(F".out", "w", stdout)
#define ll            long long
#define pb            push_back

const int N = 1e6 + 7;

using namespace std;

static ll n, m, u, v, color[N], chk[N], flag = 0;
vector<ll> a[N];

void dfs(int u)
{
    chk[u] = 1;
    int newcolor = 1 - color[u];
    for(int v: a[u])
    {
        if(color[v] == -1) color[v] = newcolor;
        else if(color[v] != newcolor) flag = 1;
        if(chk[v] == 0) dfs(v);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //READ; WRITE;
    cin >> n >> m;
    For(i, 1, m)
    {
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }
    For(i, 1, n)
    {
        if(chk[i] == 1) continue;
        fill_n(color, N, -1);
        color[i] = 1;
        dfs(i);
        if(flag == 1)
        {
            cout << n * (n - 1) / 2 - m;
            return 0;
        }
    }
    ll cnt1 = 0, cnt2 = 0;
    For(i, 1, n)
    {
        if(color[i] == 1) ++cnt1;
        else ++cnt2;
    }
    cout << cnt1 * cnt2 - m;
return 0;
}

Submission Info

Judge Result