1978 . 邀請函 (最大團)

　　這是一題最大團（最大獨立集就是補圖的最大團），而我使用常見的手法，Bron–Kerbosch algorithm。
雖說Bron–Kerbosch algorithm可以用來計算最大團。
但是實際上它是一個列舉極大團(maximal clique)的演算法，
如果我們不需要所有極大團，我們就可以對這個算法做一個優化。

以下講解是對於已經會Bron–Kerbosch algorithm的人，要是不會請先學會ＸＤ。


  BronKerbosch1(R, P, X):
       if P and X are both empty:
           report R as a maximal clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}
這是維基百科的Bron–Kerbosch algorithm虛擬碼，我們可以看到，Ｘ集合唯一的作用，就是判斷這是不是極大團。
所以我們發現，如果要算最大團，Ｘ根本沒用嘛，所以直接整個殺掉，

變成以下這樣。

  BronKerbosch1(R, P):
       if P is empty:
           report R as a clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v))
           P := P \ {v}
對，其實我只是把Ｘ刪掉而已，就這樣。

如果有機會我再補Bron–Kerbosch algorithm。
//待補

-------------------------------------------
然後是說這題還要解決二分圖的case，
藉由某定理（？），可以知道，當二分圖時。

最大點獨立＋最大邊獨立（匹配）＝Ｖ

所以只要求最大匹配就好，輕輕鬆。
同樣如果有機會我再補可以算二分圖最大匹配的增廣路算法說明。
//待補


最後，
1.由於我比較笨，時限內跑不完，所以利用時間剪枝（快要超過時間就卡掉）。
2.將degree由小到大排會跑比較快唷。

以下直接附code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int MAX_N = 80;
typedef bitset<MAX_N> bst;
typedef pair<int,int> pii;
bst N[MAX_N],empty;
int n,m,ans;
void BKB(bst R,bst P) {
 if (P==empty){
  ans=max(ans,(int)R.count());
  return;
 }
 if ((R|P).count()<=ans) return;
 if (double(clock())/CLOCKS_PER_SEC > 0.199) return;
 int u=P._Find_first();
 bst now=P&~N[u];
 for (int i=now._Find_first();i<n;i=now._Find_next(i)) {
  R[i]=1;
  BKB(R,P&N[i]);
  R[i]=0;
  P[i]=0;
 }
 return;
}
vector<pii> v;
bool bi(){
 if(n/2%2) return 0;
 for(pii ii:v)
  if(ii.F>=n/2||ii.S<n/2) return 0;
 return 1;
}
int ym[80];
bitset<80> arv;
bool DFS(int x){
 for(int i=n/2;i<n;i++)
  if(N[x][i]&&!arv[i]){
   arv[i]=1;
   if(ym[i]==-1||DFS(ym[i])){
    ym[i]=x;
    return 1;
   }
  }
 return 0;
}
int match(){
 memset(ym,-1,sizeof ym);
 int cnt=0;
 for(int i=0;i<n/2;i++){
  arv.reset();
  if(DFS(i))
   cnt++;
 }
 return cnt;
}
int deg[MAX_N];
int rev[MAX_N];
int main(){
 srand(time(0));
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 bst x; x.reset();
 int tmp[n];
 for(int i=0;i<n;++i){
  x[i]=1;
  tmp[i]=i;
  N[i].set();
  N[i][i]=0; 
 }
 while(m--){
  int a,b; cin>>a>>b;
  if(a>b) swap(a,b);
  v.emplace_back(a,b);
  deg[a]++;
  deg[b]++;
 }
 if(bi()){
  for(int i=0;i<n;i++)
   N[i].reset();
  for(pii ii:v)
   N[ii.F][ii.S]=N[ii.S][ii.F]=1;
  cout<<n-match()<< '\n';
  return 0;
 }
 
 sort(tmp,tmp+n, [&](const int &a, const int &b) { return deg[a] < deg[b]; });
 for(int i=0;i<n;i++){
  rev[tmp[i]]=i;
 }
 for(pii ii:v){
  ii.F=rev[ii.F]; ii.S=rev[ii.S];
  N[ii.F][ii.S]=N[ii.S][ii.F]=0;
 }
 BKB(empty,x);
 cout<<ans<< '\n';
}