Submission #2544989

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

int N, M, A[100009], B[100009], col[100009], z[2]; vector<int>x[100009]; bool OK = false;

void dfs(int pos, int depth) {
	if (col[pos] >= 0) {
		if (col[pos] != depth) OK = true;
		return;
	}
	col[pos] = depth; z[depth]++;
	for (int i = 0; i < x[pos].size(); i++) dfs(x[pos][i], depth ^ 1);
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		x[A[i]].push_back(B[i]);
		x[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) col[i] = -1;
	dfs(1, 0);
	long long G1 = 1LL * z[0] * z[1];
	if (OK == true) G1 = 1LL * N*(N - 1) / 2LL;
	cout << G1 - M << endl;
	return 0;
}

Submission Info

Judge Result