ABC002 D - 派閥

Calendar Clock iconCalendar Clock icon


Table of contents

# Problem

# Input

x1y1x_1 y_1
x2y2x_2 y_2
xMyMx_M y_M

  • NN - The number of people
  • MM - The number of relationship
  • xiyix_i y_i - xix_i and yiy_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 NN 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


# 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;
  if (shouldAdd) max_ = max(max_, dfs(n + 1, members));
  return max_;

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

int main(void) {
  return 0;

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!