Submission #70043998

---

Source Code Expand

#include<iostream> 
#include<algorithm> 
#include<vector> 
#include<string>
#include<queue>
using namespace std;

int n, m;
vector<int> graph[11];
int ret = 987654321;

void check(int mask) {
	bool team[11];
	for (int i = 0; i < n; i++) {
		if ((mask & (1 << i)) != 0) team[i + 1] = true;
		else team[i + 1] = false;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int next : graph[i]) {
			if (!(team[i] ^ team[next])) {
				cnt++;
			}
		}
	}
	ret = min(cnt / 2, ret);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int mask = 0; mask < (1 << n); mask++) {
		check(mask);
	}
	cout << ret;
}

Submission Info

Judge Result