#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using std::vector;

//DECLARATIONS

void Genmatrix(long i);
int IsThick(void);
void Squares(void);
bool Union(void);
bool CheckThick(void);
void Cliques(void);
void Nextvert(vector < int >clique);

//The adjacency matrix:

vector<vector<char> > Adj;

//The vector that will hold thick subgraphs; each graph is a length-n row whose entries are 1 or 0 according to whether the corresponding vertex is in the subgraph:

vector<vector<char> > Thick;

//The number of vertices is n; the number of cliques is clq.

int n;
long clq;
int clqtemp;

main(int argc, char \ast argv[])
{   n = atoi(argv[1]);  //Retrieves the number of vertices from the command line.

    //The following lines declare Adj as an n-by-n matrix.

    Adj.resize(n);
    for (int j = 0; j < n; ++j)
      Adj[j].resize(n);

    long count = 0;

    //For all i at most the number of graphs on a given size-n vertex set, build the adjacency matrix of the i^th graph.  This is accomplished by the function Genmatrix().  The resulting graph is then passed to the function IsThick(), which determines whether it is in the class of thick graphs.  IsThick() returns 1 or 0 according to thickness of the graph, so the variable count is increased by 1 if the graph was thick.  Thus count keeps a count of the number of thick graphs.

    for (long i = 0; i < (long) pow(2.0, n \ast (n - 1) / 2); i++) {
        Genmatrix(i);
        int add = IsThick();
        count += add;

        //If the graph was thick, count how many cliques it contains.  This number is clqtemp, which is added to the running total clq of cliques in thick graphs. We don't keep track of 0- and 1-cliques for the moment.

        if (add == 1) {
            clqtemp = 0;
            Cliques();
            clq += clqtemp;}}

    //Now we add 0- and 1-cliques, i.e. the empty set and the vertices.

    clq=clq+count\ast(n+1);

    //Print the number of thick graphs with a given set of n vertices (i.e. t(n)) and the number of cliques in the disjoint union of all such graphs (i.e. c(n)).

    printf("There are %ld thick graphs with %d vertices\n", count, n);
    printf("There are %ld cliques\n", clq);
}

void Genmatrix(long i)
{    //This function builds the i^th n-by-n symmetric matrix.

     for (int j = 0; j < n; j++) {
        for (int k = 0; k < j; k++) {
            Adj[j][k] = i % 2;
            Adj[k][j] = Adj[j][k];
            i = (long) (i - i % 2) / 2;}}
}

int IsThick()
{   //This function tests a graph for thickness.

    //First, we find all of the induced K_{2,2} subgraphs, and load them into the matrix Thick:

    Squares();

    //If there were no squares, then there are no thick subgraphs, so return 0

    if (Thick.size() == 0)
        return 0;
    else {
        bool u = true;

        //Start taking thick unions and coning off vertices.  Continue to do this (using the function Union) as long as Union is doing things.  Union operates on Thick.

        while (u)
             u = Union();

        //Check if the first line of Thick is all ones, i.e. there is a thick induced subgraph containing all vertices.  If so, return 1.  Otherwise, return 0.

        if (CheckThick())
             return 1;
        else
             return 0;}
}

void Squares()
{   //Clear Thick; we will fill this matrix with squares!  s keeps track of which line of Thick we're in.

    Thick.clear();
    int s = 0;

    //Proceed through all possible pairs of distinct vertices, keeping symmetry in mind.

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

              //We're looking for adjacent i,j; these will form one edge of our square.  Having found such a pair, find a new vertex k that is adjacent to j and not adjacent to i.  Given such a vertex, find a vertex l that completes the square.  Change the current line of Thick to the vector with 1s in the i,j,k,l places and 0s elsewhere.  Move to the next line of Thick and start again.

              if (Adj[i][j] == 1) {
              for (int k = i + 1; k < n; k++) {
                   if (Adj[j][k] == 1 && Adj[i][k] == 0) {
                        for (int l = j + 1; l < n; l++) {
                             if (Adj[i][l] == 1 && Adj[k][l] == 1
                                 && Adj[j][l] == 0) {
                                 s++;
                                 Thick.resize(s);
                                 Thick[s - 1].resize(n);
                                 Thick[s - 1][i] = 1;
                                 Thick[s - 1][j] = 1;
                                 Thick[s - 1][k] = 1;
                                 Thick[s - 1][l] = 1;}}}}}}}
}

bool Union()
{   //This function recognizes new thick subgraphs, given old ones, and modifies Thick accordingly.


    //The variable u is true if we've just performed a non-identity operation on Thick, and false otherwise.  We continue doing operations until u=false.  Again, s is the number of thick subgraphs, i.e. the number of rows in Thick.

    bool u = false;
    int s = Thick.size();

    //Iterate over all pairs of distinct vertices, accounting for symmetry.

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

              //If i,j are non-adjacent, then...

              if (Adj[i][j] == 0) {
                  int k = 0;
                  int first = -1;

                  //...move through the lines in Thick, looking for a thick subgraph containing i and j.  "first" is the identity of the first such subgraph.  If one is found (i.e. first ends up larger than -1), then...

                  while (k < s && first == -1) {
                      if (Thick[k][i] == 1 && Thick[k][j] == 1)
                          first = k;
                      else
                          k++;}

                  //...look among all vertices for p, different from i and j, that is not in the current thick subgraph and is adjacent to i,j.  If found, modify the current row of Thick by adding p; this corresponds to coning off an aspherical subgraph.  We haven't changed the number of rows in Thick, but we've made one bigger.

                  if (first != -1) {
                      for (int p = 0; p < n; p++) {
                          if (p != i && p != j && Thick[first][p] == 0
                              && Adj[i][p] == 1 && Adj[j][p] == 1) {
                              u = true;

                              Thick[first][p] = 1;}}


                      //Remembering i,j, proceed through the rows of Thick, looking for all rows of Thick that contain i and j. Add to the current row any vertex that appears in another row containing i,j, and then remove the row you've just worked on, since its vertices are recorded in the current row Thick[first].

                      while (k < s - 1) {
                         k++;
                         if (Thick[k][i] == 1 && Thick[k][j] == 1) {
                             u = true;
                             for (int p = 0; p < n; p++) {
                                  if (Thick[k][p] == 1)
                                      Thick[first][p] = 1;

                                      Thick[k][p] = Thick[s - 1][p];}
                                      s--;}}}}}}

    Thick.resize(s);
    return u;
}

bool CheckThick()
{   //Return true if and only if the first line of Thick is all 1s.

    int k = 0;
    int j = 0;

    do {
        if (Thick[0][j] == 0)
            k = 1;
            j++;
    } while (k == 0 && j < n);

    if (k == 0)
        return true;
    else
        return false;
}

void Cliques()
{   vector < int >clique;

    //For each j, clear the vector clique, add a new component equal to j, and call Nextvert.  This passes a 1-clique to Nextvert, which will find all cliques containing that clique.

    for (int j = 0; j < n; j++) {
         clique.clear();
         clique.push_back(j);
         Nextvert(clique);}
}

void Nextvert(vector < int >clique)
{   //This function accepts a s-dimensional 0 vector clique, whose entries are the vertices in some clique. The variable j is the last entry in clique.

    int s = clique.size();
    int j = clique[s - 1];

    //For all i between the last entry in clique and the size of the graph, check that the i^th vertex is adjacent to all of the vertices indexed by entries in clique.  If there's a nonadjacency, then adding i won't produce a larger clique, so move to the next i.  Otherwise, put a new entry in clique, equal to i, increment the number of cliques by 1, and pass the new vector to this function.  This terminates at a maximal clique, whereupon we pop up to the previous level of recursion, finish _that_ loop, etc.  In other words, given a clique, this function eventually counts all cliques (with at least two vertices) containing that clique.

    for (int i = j + 1; i < n; i++) {
         bool u = true;

         for (int p = 0; p < s; p++) {
              if (Adj[clique[p]][i] == 0)
                  u = false;}

         if (u) {
            clique.resize(s);
            clique.push_back(i);
            clqtemp++;
            Nextvert(clique);}}
}