Submission #1981628

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
    int N, M;
    if (scanf("%d%d", &N, &M) < 2) return 0;

    vector< vector<bool> > matrix(N, vector<bool>(N, false));

    for (int i = 0; i < M; i++)
    {
        int x, y;
        if (scanf("%d%d", &x, &y) < 2) return 0;
        x--;
        y--;
        matrix[x][y] = true;
        matrix[y][x] = true;
    }

    vector<int> clique(1 << N, 0);

    int ans = 1;

    // 自分は自分の派閥
    for (int i = 0; i < N; i++) clique[1 << i] = 1;

    for (int i = 0; i < 1 << N; i++)
    {
        if (clique[i] == 0) continue;

        for (int j = 0; j < N; j++)
        {
            // j 派閥に加えられていない
            if ((i & 1 << j) == 0)
            {
                bool canadd = true;

                // 派閥に含まれるすべての議員と
                // 互いに知り合いかどうか
                for (int k = 0; k < N; k++)
                {
                    // k 番目の人は 派閥に加えられているか
                    if ((i & 1 << k) == 0) continue;

                    // j 番目の人は k 番目の人と知り合いでない
                    if (matrix[j][k] == false)
                    {
                        canadd = false;
                        break;
                    }
                }

                // 派閥に含まれるすべての議員と知り合いである
                if (canadd)
                {
                    clique[i | 1 << j] = clique[i] + 1;
                    ans = max(ans, clique[i | 1 << j]);
                }
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

Submission Info

Judge Result