Bron Kerbosch algorithm for maximal clique

bron-kerbosch.cpp

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

int n;
vector<ll> v, ne;

// ne[u] is the neighbours of u
// v is the result
void BronKerbosch(ll R, ll P, ll X){
  if ((P == 0LL) && (X == 0LL)) {v.push_back(R);return;}
	int u = 0;
	for (; u < n; u ++) if ( (P|X) & (1LL << u) ) break;
	for (int i = 0; i < n; i ++)
		if ( (P&~ne[u]) & (1LL << i) ){
			BronKerbosch(R | (1LL << i), P & ne[i], X & ne[i]);
			P -= (1LL << i); X |= (1LL << i);
		}
}

int cal(ll P, vector<int> mp){
	int ans(0), i(0);
	while(P){
		if (P&1LL) ans += mp[i];
		P >>= 1;
		i ++;
	}
	return ans;
}

class MagicMolecule{
	public:
	int maxMagicPower(vector<int> mp, vector<string> mb){
		n = mp.size();
		v.clear();
		ne.clear();
		ne.resize(n, 0);
		for (int i = 0; i < n; i ++)
			for (int j = 0; j < n; j ++)
				if (mb[i][j] == 'Y')
					ne[i] |= (1LL<<j);
		BronKerbosch(0, ~0LL, 0);
		for (int i = 0; i < v.size(); i ++) cout << v[i] << endl;
		int ans = -1;
		for (int i = 0; i < v.size(); i ++)
			if (3*__builtin_popcountll(v[i]) >= 2*n)
				ans = max(ans, cal(v[i], mp));
		return ans;
	}
};