题解 CF1364D 【Ehab's Last Corollary】

【CF1364D】 Ehab's Last Corollary

Analysis

有点诡异的题，可能需要一点灵光乍现？（

出于一些灵光，我们首先考虑 k = n 的情况。构造答案很简单：

• 如果图是一棵树，那么直接对图进行黑白染色，显然同色结点构成了一个独立集，因此输出那个 size 不小于 \left \lceil \frac k 2 \right \rceil 的集合的前 \left \lceil \frac k 2 \right \rceil 个元素即可。
• 否则因为是连通图，图上一定存在环，大小显然不大于 k，因此直接输出这个环即可。

现在考虑 n > k 的情况。注意到题目描述中“I have a proof that for any input you can always solve at least one of these problems”，因此给定的图的任一大小为 k 的子图一定能找到解。因此我们在原图上随便选一个节点数为 k 的连通块，然后问题就转化为了 k = n 的情况，按照上面叙述找答案即可。

找环的方法是，从某个节点开始 dfs，用栈维护 dfs 树上当前节点到根的所有节点。如果在 dfs 过程中找到了下一个结点 v 在栈里，那么当前栈顶元素到 v 之间的所有节点构成了一个环。

Code

namespace Fusu {

const int maxn = 200005;

int n, m, t, cnt = 1;
bool vis[maxn];
std::pair<int, int> edge[maxn];
std::vector<int> e[maxn], ans[2];
std::queue<int> Q;

void dfs(const int u, const int v);
void dfs(const int u, const int v, const int fa);

void Main() {
  qr(n); qr(m); qr(t);
  for (int i = 1; i <= m; ++i) {
    qr(edge[i].first); qr(edge[i].second);
    e[edge[i].first].push_back(edge[i].second);
    e[edge[i].second].push_back(edge[i].first);
  }
  Q.push(1);
  vis[1] = true;
  while (cnt != t) {
    int u = Q.front(); Q.pop();
    for (auto v : e[u]) if (vis[v] == false) {
      vis[v] = true;
      Q.push(v);
      if (++cnt == t) break;
    }
  }
  for (int i = 1; i <= n; ++i) {
    e[i].clear();
  }
  int ecnt = 0;
  for (int i = 1; i <= m; ++i) {
    int u = edge[i].first, v = edge[i].second;
    if (vis[u] && vis[v]) {
      ++ecnt;
      e[u].push_back(v);
      e[v].push_back(u);
    }
  }
  memset(vis, 0, sizeof vis);
  if (ecnt == (t - 1)) {
    puts("1");
    dfs(1, 0, 0);
    int v = 0;
    int tt = t >> 1;
    if (t & 1) ++tt;
    if (ans[v].size() < tt) v = 1;
    for (int i = 0; i < tt; ++i) qw(ans[v][i], ' ');
    putchar('\n');
  } else {
    puts("2");
    dfs(1, 0);
  }
}

void dfs(const int u, const int w, const int fa) {
  ans[w].push_back(u);
  for (auto v : e[u]) if (v != fa) {
    dfs(v, w ^ 1, u);
  }
}

int top;
int stk[maxn];
std::vector<int> a;
void dfs(const int u, const int fa) {
  stk[++top] = u;
  vis[u] = true;
  for (auto v : e[u]) if (v != fa) {
    if (vis[v]) {
      while (stk[top] != v) {
        a.push_back(stk[top--]);
      }
      a.push_back(v);
      qw(a.size(), '\n');
      for (auto u : a) qw(u, ' ');
      putchar('\n');
      exit(0);
    } else {
      dfs(v, u);
    }
  }
  --top;
}

} // namespace Fusu