Submission #4065196

---

Source Code Expand

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

vector<ll> G[101010];
vector<ll> mark(101010, -1);

bool is_bipartite(ll now, ll now_mark){
	if(mark[now]!=-1) return (mark[now]==now_mark);
	mark[now] = now_mark;
	bool flag = true;
	REP(i, G[now].size()){
		ll next = G[now][i];
		flag &= is_bipartite(next, 1-now_mark);
	}
	return flag;
}

int main(){
	ll N, M;
	cin >> N >> M;
	REP(i, M){
		ll a, b;
		cin >> a >> b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	bool flag = is_bipartite(0, 1);
	if(flag){
		ll sum = 0;
		REP(i, N) sum += mark[i];
		ll res = 0;
		REP(i, N){
			if(mark[i]==0){
				res += (sum - G[i].size());
			}
		}
		cout << res << endl;
	}else{
		cout << N*(N-1)/2 - M << endl;
	}

    return 0;
}

Submission Info

Judge Result