Submission #111870

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

bool can(const std::vector<std::vector<bool> > &R, int N, int pattern)
{
	for (int i = 0; i < N; ++i) if (pattern & (1 << i))  {
		for (int j = i + 1; j < N; ++j) if (pattern & (1 << j)) {
			if (!R[i][j]) {
				return false;
			}
		}
	}
	return true;
}

int main()
{
	int N, M;
	std::cin >> N >> M;

	std::vector<std::vector<bool> > R(N, std::vector<bool>(N, false));

	for (int i = 0; i < M; ++i) {
		int x, y;
		std::cin >> x >> y;
		R[x - 1][y - 1] = true;
		R[y - 1][x - 1] = true;
	}
	size_t result = 0;
	for (int i = 0; i < (1 << N); ++i) {
		if (can(R, N, i)) {
			result = std::max(result, std::bitset<32>(i).count());
		}
	}
	std::cout << result << std::endl;
}

Submission Info

Judge Result