阿斯蒂芬

Nuisdete · 2023-06-26 14:54:12 · 题解

题目要求的是弦图的色数。

首先设 N(x) 表示在完美消除序列中在 x 后面且和 x 关联的点的集合，那么最大团大小就是 \max_{u \in V}{|N(u)|} + 1。这个证明可以参考其它资料。

下界显然是最大团大小，考虑构造一组方案取到下界。

按照完美消除序列从后往前贪心染色就可以取到下界，具体证明大概就是染 u 这个点的时候，影响它颜色的只是染过色且与它关联的点，不难发现这些点就是 N(u)，那么色数显然也就是上面的那个最大团的式子了。

求 |N(u)| 用 mcs 算法就行了。

# include <cstdio>
# include <vector>
# include <algorithm>

using std::max;

const int MAXN = 1e4 + 5;

int n, m;

int deg[MAXN << 1];
bool vis[MAXN << 1];

std::vector<int> G[MAXN << 1], vec[MAXN << 1];

void mcs() {
  int p = 0;
  for (int i = 1; i <= n; ++i) 
    vec[0].push_back(i);

  for (int i = 1; i <= n; ++i) {
    int cur = 0;
    while (!cur) {
      while (!vec[p].empty() && vis[ vec[p].back() ])
        vec[p].pop_back();

      if (vec[p].empty()) --p;
      else cur = vec[p].back();
    }
    vis[cur] = true;
    for (int k : G[cur]) if (!vis[k]) {
      ++deg[k];
      if (deg[k] > p) ++p;
      vec[ deg[k] ].push_back(k);
    }
  }
}

int main() {

  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    G[x].push_back(y), G[y].push_back(x);
  }
  mcs();
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    ans = max(ans, deg[i] + 1);

  printf("%d\n", ans);

  return 0;
}