ABC 002 D - 派閥

• 問題

atcoder.jp

• 解法

最大クリークを求める問題 (無向グラフGのクリークとはGの完全部分グラフ(の頂点集合)のこと).
頂点数が少ないので全ての部分グラフを見てあげることができる.
全列挙にはbitを使うのが便利.

#include <iostream>
#include <vector>
#include <set>


using namespace std;

typedef pair<int,int> P;


int main()
{
	int n,m;
	cin >> n >> m;
	vector<P> rel(m);
	for(int i = 0; i < m; i++){
		cin >> rel[i].first >> rel[i].second;
		rel[i].first--;
		rel[i].second--;
	}

	int ans = 1;
	for(int bit = 0; bit < (1<<n); bit++){
		set<int> S;
		for(int i = 0; i < n; i++){
			if(bit & (1<<i)) S.insert(i);
		}

		int edge = 0;
		for(int i = 0; i < m; i++){
			if(S.count(rel[i].first) && S.count(rel[i].second)) edge++;
		}
		if(edge == S.size()*(S.size()-1)/2) ans = max(ans,(int)S.size());
	}
	cout << ans << endl;

	return 0;
}