abc002_4

結構苦労した.

グループとなり得るパターンはn人をそれぞれbitのi番目に存在するか否かで考えると0000....000から1111....1111の2^nで表せれる

あとは適当な2人がグループのパターンに沿っている かつ 知り合いならばok

違うならngという感じで探していく

最大クリーク問題を求める問題を考えることと同じらしい

(無向グラフの中で最大な完全グラフを探し出す問題)

関係ないけれども完全グラフといえばヨビノリさんのこれが好き

www.youtube.com

#include<bits/stdc++.h>

using namespace std;

int n, m;

bool p[22][22];

int main(){

    cin >> n >> m;

    for(int i=0;i<m;i++){

        int x, y;

        cin >> x >> y;

        x--; y--;

        p[x][y] = p[y][x] = true;

    }

    int ans = 0;

    for(int i=0;i<(1<<n);i++){

        int bit = i;

        bool flg = true;

        for(int j=0;j<n;j++){

            for(int k=j+1;k<n;k++){

                if(((bit>>j)&1) && ( (bit>>k)&1) && !p[j][k]) flg = false;

            }

        }

       

        int cnt = 0;

        if(flg){

            for(;bit;bit&=(bit-1)) cnt++;

        }

        ans = max(ans, cnt);

    }

    cout << ans << endl;

}