oToToT

maxclique dyn

Sep 27th, 2020
786
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <bitset>
  4. #include <numeric>
  5. #include <vector>
  6.  
  7. const int kN = 100;
  8. const double kT = 0.025;
  9. int s[kN + 1], t[kN + 1], deg[kN], steps;
  10. std::bitset<kN> Q, Qmax;
  11. std::vector<int> z[kN];
  12. std::bitset<kN> adj[kN];
  13.  
  14. std::vector<int> ColorSort(std::vector<int> &R) {
  15.   int kmin = Qmax.count() - Q.count() + 1;
  16.   if (kmin < 1) kmin = 1;
  17.   int kmax = 1;
  18.   int j = 0;
  19.   z[1].clear(), z[2].clear();
  20.   for (int i = 0; i < R.size(); ++i) {
  21.     int p = R[i];
  22.     int k = 1;
  23.     while (true) {
  24.       bool tc = false;
  25.       for (int u : z[k]) tc |= adj[p].test(u);
  26.       if (tc)
  27.         ++k;
  28.       else
  29.         break;
  30.     }
  31.     if (k > kmax) {
  32.       kmax = k;
  33.       z[kmax + 1].clear();
  34.     }
  35.     z[k].push_back(p);
  36.     if (k < kmin) R[j++] = R[i];
  37.   }
  38.   std::vector<int> C(R.size());
  39.   if (j > 0) C[j - 1] = 0;
  40.   for (int k = kmin; k <= kmax; ++k) {
  41.     for (int u : z[k]) {
  42.       assert(j < R.size());
  43.       R[j] = u;
  44.       C[j] = k;
  45.       j++;
  46.     }
  47.   }
  48.   return C;
  49. }
  50.  
  51. void MaxCliqueDyn(const std::vector<int> &R, const std::vector<int> &C,
  52.                   int depth) {
  53.   s[depth] += s[depth - 1] - t[depth];
  54.   t[depth] = s[depth - 1];
  55.   for (int i = R.size() - 1; i >= 0; --i) {
  56.     int p = R[i];
  57.     if (Q.count() + C[i] > Qmax.count()) {
  58.       Q.set(p);
  59.       bool ok = false;
  60.       std::vector<int> v;
  61.       for (int j = 0; !ok && j < i; ++j) {
  62.         if (adj[p].test(R[j])) v.push_back(R[j]);
  63.       }
  64.       if (!v.empty()) {
  65.         if (s[depth] < kT * steps) {
  66.           for (int j = 0; j < v.size(); ++j) deg[v[j]] = 0;
  67.           for (int j = 0; j < v.size(); ++j) {
  68.             for (int k = 0; k < v.size(); ++k) {
  69.               if (adj[v[j]].test(v[k])) deg[v[j]]++;
  70.             }
  71.           }
  72.           std::sort(v.begin(), v.end(),
  73.                     [&](int x, int y) { return deg[x] > deg[y]; });
  74.         }
  75.         auto Cp = ColorSort(v);
  76.         s[depth]++;
  77.         steps++;
  78.         MaxCliqueDyn(v, Cp, depth + 1);
  79.       } else if (Q.count() > Qmax.count()) {
  80.         Qmax = Q;
  81.       }
  82.       Q.reset(p);
  83.     } else {
  84.       return;
  85.     }
  86.   }
  87. }
  88.  
  89. int main() {
  90.   int n;
  91.   scanf("%d", &n);
  92.   for (int i = 0; i < n; ++i) {
  93.     for (int j = 0; j < n; ++j) {
  94.       if (i != j) adj[i].set(j);
  95.     }
  96.   }
  97.   int m;
  98.   scanf("%d", &m);
  99.   for (int i = 0; i < m; ++i) {
  100.     int u, v;
  101.     scanf("%d%d", &u, &v);
  102.     adj[u].reset(v);
  103.     adj[v].reset(u);
  104.   }
  105.   std::vector<int> R(n);
  106.   std::iota(R.begin(), R.end(), 0);
  107.   auto C = ColorSort(R);
  108.   // for (int i = 0; i < n; ++i) printf("%d ", C[i]);
  109.   // puts("");
  110.   // for (int i = 0; i < n; ++i) printf("%d ", R[i]);
  111.   // puts("");
  112.   MaxCliqueDyn(R, C, 1);
  113.   printf("%d\n", (int)Qmax.count());
  114. }
RAW Paste Data