Table of contents

• Problem
  • Input
  • Output
• Explanation
• Time complexity
• Solution

# Problem

https://atcoder.jp/contests/abc002/tasks/abc002_4

# Input

$N M$
$x_1 y_1$
$x_2 y_2$
...
$x_M y_M$

• $N$ - The number of people
• $M$ - The number of relationship
• $x_i y_i$ - $x_i$ and $y_i$ know each other

# Output

The maximum size of possible groups.
A group consists of members who know each other directly.

# Explanation

It can be solved with bit exhaustive search as $N$ is enough small.
There are 2 choices for each member.
In case you choose to add a member to a group, you have to confirm that the member knows each existing member from the group directly.
If you reprecent the relationship as a graph, it's easy to answer this question.
The only thing you have to do is check if a edge between 2 exists.

By the way, this problem is an instance of Clique problem.

the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found.

# Time complexity

$O(2^N)$

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 12
#define MAX_M (MAX_N * (MAX_N-1) / 2)

Int N, M;
Int G[MAX_N][MAX_N];

void input() {
  Int x, y;
  cin >> N >> M;
  loop(x,0,MAX_N) {
    loop(y,x + 1,MAX_N) {
      G[x][y] = G[y][x] = 0;
    }
  }
  loop(m,0,M) {
    cin >> x >> y;
    x--, y--;
    G[x][y] = G[y][x] = 1;
  }
}

Int dfs(Int n, vector<Int> members) {
  if (n >= N) return members.size();
  Int max_ = -1;
  // Skip the member
  max_ = max(max_, dfs(n + 1, members));
  // Add the member if possible
  bool shouldAdd = true;
  // shouldAdd <=> n is connected to all the existing members
  for (auto m: members) {
    if (G[m][n] == 0 || G[n][m] == 0) shouldAdd = false;
  }
  members.push_back(n);
  if (shouldAdd) max_ = max(max_, dfs(n + 1, members));
  return max_;
}

void solve() {
  vector<Int> members;
  cout << dfs(0, members) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}