Submission #111461

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
bool relation[13][13];
bool member[13];
int memo[1<<12];
int n;

unsigned int hash(){
	unsigned int res = 0;
	for(int i=0; i<n; i++){
		if( member[i+1] ){
			res |= (1<<i);
		}
	}
	return res;
}

int solve(int k){
	for(int i=1; i<=n; i++){
		if( member[i] && !relation[k][i] ){
			return 0;
		}
	}
	if( memo[hash()] != -1 ){
		return memo[hash()];
	}
	int res = 1;
	for(int i=1; i<=n; i++){
		if( !member[i] ){
			member[i] = true;
			res = max( res, 1+solve(i) );
			member[i] = false;
		}
	}
	memo[hash()] = max( memo[hash()], res );
	return res;
}

int main(){
	int m;
	cin >> n >> m;
	memset( memo, -1, sizeof(memo) );
	rep(i,n+1)	rep(j,n+1)	relation[i][j] = false;
	rep(i,n+1)	relation[i][i] = true;
	rep(i,m){
		int x, y;
		cin >> x >> y;
		relation[x][y] = relation[y][x] = true;
	}
	int mx = 0;
	for(int i=1; i<=n; i++){
		rep(j,n+1)	member[j] = false;
		member[i] = true;
		int s = solve(i);
		if( s > mx )	mx = s;
	}
	cout << mx << endl;
	return 0;
}

Submission Info

Judge Result