D - 派閥

時間制限 : 2sec / メモリ制限 : 64MB

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。派閥に含まれるすべての議員は互いに知り合いでなければなりません。高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

Note

最大クリーク問題やん無理やんと一瞬思うけどNが小さいからbitとかつかって全探索すればとけちゃう

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
template<typename A, size_t N, typename T>

void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    ll n, m;
    bool con[15][15];
    cin >> n >> m;

    Fill(con, false);

    for (int i = 0; i < m; ++i)
    {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        con[x][y] = true;
        con[y][x] = true;
    }

    ll ans = 0;
    for (int i = 0; i < 1<<n ; ++i)
    {
        vector<ll> v;
        ll tmp = 0;
        for (int j = 0; j < n; ++j)
        {
            if(1 & i>>j){
                v.push_back(j);
                tmp++;
            }
        }

        for (int k = 0; k < v.size(); ++k)
        {
            for (int l = k+1; l < v.size(); ++l)
            {
                if(!con[v[k]][v[l]]){

                    tmp = 0;
                    goto BREAK_LABEL;
                }
            }
        }
        BREAK_LABEL:

        v.clear();
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 002 #19

D - 派閥

問題文

Note