/*
Given an undirected graph, max_clique() returns the size of the maximum clique,
that is, the largest subset of nodes such that all pairs of nodes in the subset
are connected by an edge. max_clique_weighted() additionally uses a global array
w[] specifying a weight value for each node, returning the clique in the graph
that has maximum total weight.
Both functions apply to a global, pre-populated adjacency matrix adj[] which
must satisfy the condition that adj[u][v] is true if and only if adj[v][u] is
true, for all pairs of nodes u and v respectively between 0 (inclusive) and the
total number of nodes (exclusive) as passed in the function argument. Note that
max_clique_weighted() is an efficient implementation using bitmasks of unsigned
64-bit integers, thus requiring the number of nodes to be less than 64.
Time Complexity:
- O(3^(n/3)) per call to max_clique() and max_clique_weighted(), where n
is the number of nodes.
Space Complexity:
- O(n^2) for storage of the graph, where n is the number of nodes.
- O(n) auxiliary stack space for max_clique() and max_clique_weighted().
*/

#include "stdafx.h"
#include <algorithm>
#include <bitset>
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <time.h>
#include <cassert>

using namespace std;
const int MAXN = 10;
bool** adj;
int k,u;

/* Максимальная клика
ПРОЦЕДУРА extend (candidates, not):
ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1 Выбираем вершину v из candidates и добавляем её в compsub
2 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
3 ЕСЛИ new_candidates и new_not пусты
4 ТО compsub – клика
5 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)
6 Удаляем v из compsub и candidates, и помещаем в not

Максимальное по включению независимое множество вершин
1 Условие в основном цикле: not не должно содержать ни одной вершины, НЕ СОЕДИНЕННОЙ НИ С ОДНОЙ из вершин во множестве candidates
2 Для формирования new_candidates и new_not, необходимо удалять из candidates и not вершины, СОЕДИНЕННЫЕ с выбранной вершиной.

*/
int rec(int nodes, std::bitset<MAXN> &curr, std::bitset<MAXN> &pool, std::bitset<MAXN> &excl) {
    cout << u << " current " << curr<<" pool "<<pool<<" exclusion "<<excl;
    if (pool.none() && excl.none()) {//ЕСЛИ new_candidates и new_not пусты, ТО compsub – клика
        return curr.count();//величина локального множества
    }
    int ans=0;
    u = 0;
    for (int v = 0; v < nodes; v++) {
        if ((pool[v] && !excl[v])) {
            u = v;
        }
    }
    for (int v = 0; v < nodes; v++) {
        if ((!pool[v] || adj[u][v])) {
            continue;
        }
        std::bitset<MAXN> ncurr, npool, nexcl;
        for (int i = 0; i < nodes; i++) {
            ncurr[i] = curr[i];
        }
        ncurr[v] = true;
        for (int j = 0; j < nodes; j++) {
            npool[j] = pool[j] && !adj[v][j];//Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v
            //nexcl[j] = excl[j] && adj[v][j];//Для формирования new_candidates и new_not, необходимо удалять из candidates и not вершины, СОЕДИНЕННЫЕ с выбранной вершиной.
        }
        npool[v] = false;
        cout << " ncurr " << ncurr << " npool " << npool << " nexcl " << nexcl<<endl;
        cout << endl;
        ans = std::max(ans, rec(nodes, ncurr, npool, nexcl));
        pool[v] = false;//для ускорения
        excl[v] = true;
    }
    return ans;
}

int max_clique(int nodes) {
    std::bitset<MAXN> curr, excl, pool;
    pool.flip();
    return rec(nodes, curr, pool, excl);
}

void add_edge_true(int u, int v) {
    adj[u][v] = true;
    adj[v][u] = true;
}

void add_edge_false(int u, int v) {
    adj[u][v] = false;
    adj[v][u] = false;
}

void fileread(string word) {//Считывание матрицы из файла
    int l;
    ifstream in(word);
    if (in.is_open())
    {
        in >> k;
        adj = new bool*[k];
        for (int i = 0; i < k; i++)
            adj[i] = new bool[k];
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
            {
                in >> l;
                if (l != 0)
                {
                    add_edge_true(i, j);
                }
                else{
                    add_edge_false(i, j);
                }
            }
        in.close();
        cout << "File readed" << endl;
    }
    else
    {
        //Если открытие файла прошло не успешно
        cout << "File not found" << endl;
    }
}

int main() {
        string file;
    cout << "Vvedite imya fila" << endl;
    cin >> file;
    fileread(file);
    float fTimeStart = clock() / (float)CLOCKS_PER_SEC;
    cout <<endl<<"Chislo vershin "<< max_clique(k) << endl;
    float fTimeStop = clock() / (float)CLOCKS_PER_SEC;
    long double time = (fTimeStop - fTimeStart);
    printf("Dlitelnost %f secund \n", time);
    return 0;
}