Submission #1691602

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll n, m, color[100000], ans;
vector<int>g[100000];

bool vipartiteGraph(int node, int c) {
	color[node] = c;
	bool res = true;
	for (int i = 0; i < g[node].size(); i++) {
		if (color[g[node][i]] == INT32_MAX) {
			res = res && vipartiteGraph(g[node][i], (c+1)%2);
		}
		else if (color[g[node][i]] == c) {
			res = false;
		}
	}

	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}

	for (int i = 0; i < n; i++)color[i] = INT32_MAX;

	if (vipartiteGraph(0, 0)) {//二部グラフであったら
		//cout << "二部グラフである" << endl;

		ll brack = 0, white = 0;
		for (int i = 0; i < n; i++) {
			if (color[i] == 0)brack++;
			else white++;
		}
		ans = brack*white-m;
		//cout << "brack:" << brack << " white:" << white << endl;
	}
	else {//二部グラフでなかったら
		//cout << "二部グラフでない" << endl;
		ans = n*(n - 1) / 2 - m;
	}

	cout << ans << endl;
}

Submission Info

Judge Result