Submission #37344296

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double PI = acos(-1);



int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> to(n);
    dsu d(n);
    vector<P> edges;
    rep(i,m) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        edges.emplace_back(u, v);
        to[u].push_back(v);
        to[v].push_back(u);
        d.merge(u,v);
    }

    int groupnum = 0;
    rep(i,n) {
        if (d.leader(i) == i) groupnum++;
    }

    vector<int> color(n, -1);

    auto dfs = [&](auto f, int v, int c, int p=-1) -> bool {
        color[v] = c;
        for (int u : to[v]) {
            if (u == p) continue;
            if (color[u] == c) return false;
            if (color[u] == -1 && !f(f, u, c^1, v)) return false;
        }
        return true;
    };

    rep(i,n) {
        if (d.leader(i) == i) {
            if (!dfs(dfs, i, 1)) {
                cout << 0 << endl;
                return 0;
            }
        }
    }

    map<int, P> mp;

    rep(i,n) {
        if (color[i] == 0) mp[d.leader(i)].first++;
        if (color[i] == 1) mp[d.leader(i)].second++;
    }

    vector<ll> cnt0(groupnum), cnt1(groupnum);
    int idx = 0;
    for (auto [_, p] : mp) {
        cnt0[idx] = p.first;
        cnt1[idx] = p.second;
        idx++;
    }

    ll ans = (ll)n * (n-1) / 2;
    rep(i,groupnum) {
        ans -= (ll)cnt0[i] * (cnt0[i]-1) / 2;
        ans -= (ll)cnt1[i] * (cnt1[i]-1) / 2;
    }
    // rep(i,groupnum)rep(j,i) {
    //     ans += (cnt0[i]+cnt1[i]) * (cnt0[j]+cnt1[j]);
    // }
    // for (auto [u, v] : edges) {
    //     if (!d.same(u, v)) ans--;
    //     else if (color[u] != color[v]) ans--;
    // }
    cout << ans - m << endl;
    return 0;
}

Submission Info

Judge Result