Submission #3011624

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

bool dfs(vector<vector<long long> > &adj, vector<long long> &used, long long node, long long color){

    used[node] = color;
    //cout << node << " " << color << endl;
    for(auto to : adj[node]){

        //同色なら
        if(used[to] == color) return false;
        else if(used[to] == 0){
            //見訪問なら
            long long nextcolor = color + 1;
            if(nextcolor == 3) nextcolor = 1;
            if(!dfs(adj, used, to, nextcolor)) return false;
        }
    }

    return true;
}

int main(){

    long long n, m; cin >> n >> m;
    vector<vector<long long> > adj(n);
    for(long long i = 0; i < m; i++){
        long long a, b; cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<long long> used(n, false);
    if(dfs(adj, used, 0, 1)){
        long long B = 0;
        long long R = 0;
        for(auto color : used){
            color == 1 ? B++ : R++;
        }

        cout << B * R - m << endl;
    }
    else cout << (n * (n - 1) / 2) - m << endl;
    return 0;
}

Submission Info

Judge Result