Submission #1841718

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <random>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define gcd(a,b)	__gcd__(a,b)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0
const ll inf = (ll)1e9;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

bool edge[40][40];
ll oklist[40];

int dp[1 << 25];

int main() {
	int n, m;	cin >> n >> m;
	rep(i, n)	oklist[i] = ((1LL << n) - 1)^(1LL<<i);
	rep(i, m) {
		int a, b;	cin >> a >> b;	a--;	b--;
		edge[a][b] = true;
		edge[b][a] = true;
		oklist[a] ^= (1LL << b);
		oklist[b] ^= (1LL << a);
	}
	int l = n / 2;
	int end = 1;
	rep(i, l)	end <<= 1;
	rep(i, end) {
		bool ok = true;
		rep(j, l)	if (i&(1 << j)) {
			dp[i] = max(dp[i], dp[i^(1<<j)]);
			rep(k, j)	if (i&(1 << k) && edge[j][k]) {
				ok = false;
			}
		}
		if (ok) {
			int cnt = 0;
			rep(j, l)	if (i&(1 << j))	cnt++;
			dp[i] = cnt;
		}
	}
	l = n - l;
	end = 1;
	rep(i, l)	end <<= 1;
	int ret = 0;
	rep(i, end) {
		bool ok = true;
		int mask = (1 << (n - l)) - 1;
		rep(j, l) {
			if (i&(1 << j)) {
				mask &= oklist[n - j - 1];
				rep(k, j)	if (i&(1 << k) && edge[n - j - 1][n - k - 1]) {
					ok = false;
				}
			}
		}
		if (ok) {
			int cnt = 0;
			rep(j, l)	if (i&(1 << j))	cnt++;
			ret = max(ret, cnt + dp[mask]);
		}
	}
	cout << ret << endl;
	return 0;
}

Submission Info

Judge Result