CF51F Caterpillar

· · 题解

IV. CF51F Caterpillar

初级图论。

题目要求不能存在环，我们自然地想到将所有 E-BCC 缩成一个点。缩点后整张图会变成一棵森林，先处理每一棵树，再用连通块数量 -1 次操作将它们连起来。

考虑确定主链后如何用最少的操作使得一棵树变成毛毛虫。

对于除了主链以外的节点，考虑它是否作为最终挂在主链旁边的叶子。将主链看成根，具有祖先后代关系的点对不能同时被选中作为叶子，因为此时后代和主链之间隔了一个祖先，说明它到主链的距离 \geq 2，与题意不符。

因此相当于选择最多的节点使得这些节点之间没有祖先后代关系。我们的决策是选择所有叶子，因为若一个非叶子被选，我们一定可以取消选择它，并选择它的所有儿子，这样一定更优。不断调整即可得到该结论。

因此，最终保留的节点为所有主链上的节点和我们选中作为叶子的节点。这意味着对于某条路径 P 而言，它作为主链时对应的最少操作次数为 n - |P| - L，其中 n 是树的大小，L 是主链外叶子节点的数量。

容易发现，当 P 的两端不是叶子时，我们总可以调整使得 P 的两端是叶子且 n - |P| - L 不变或变小：向任意一个可以延伸的方向延伸，每次 |P| 增加 1，但 L 要么不变（当延伸的点是非叶子），要么只减少 1（当延伸的点是叶子）。

因此，设原图的叶子数量为 K，则操作次数为 n - K + 2 - |P|。n - K + 2 是定值，我们希望 |P| 最大，自然是选取树的直径，同时恰好满足了 P 的两端是叶子的要求。

时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, m;
vector<pair<int, int>> e[N];
vector<int> g[N];
int dn, dfn[N], low[N], top, stc[N], cn, col[N];
void form(int id) {cn++; for(int x = 0; x != id; ) col[x = stc[top--]] = cn;}
void tarjan(int id, int eid) {
  stc[++top] = id, dfn[id] = low[id] = ++dn;
  for(auto _ : e[id]) {
    if(_.second == eid) continue;
    int it = _.first;
    if(!dfn[it]) {
      tarjan(it, _.second), low[id] = min(low[id], low[it]);
      if(low[it] > dfn[id]) form(it);
    }
    else low[id] = min(low[id], dfn[it]);
  }
  if(!eid) form(id);
}
int ans, comp, vis[N], dis[N];
vector<int> cur;
void find(int id) {
  cur.push_back(id), vis[id] = 1;
  for(int it : g[id]) if(!vis[it]) find(it);
}
void dfs(int id, int ff) {
  dis[id] = dis[ff] + 1;
  for(int it : g[id]) if(it != ff) dfs(it, id);
}
void deal(int id) {
  if(g[id].empty()) return ans++, void();
  cur.clear(), find(id);
  dfs(id, 0);
  int u = id, leaf = 0;
  for(int it : cur) if(dis[it] > dis[u]) u = it;
  dfs(u, 0);
  for(int it : cur) if(dis[it] > dis[u]) u = it;
  for(int it : cur) leaf += g[it].size() == 1;
  ans += dis[u] + leaf - 2;
}
int main() {
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e[u].push_back({v, i});
    e[v].push_back({u, i});
  }
  for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, 0);
  for(int i = 1; i <= n; i++)
    for(auto _ : e[i])
      if(col[i] != col[_.first])
        g[col[i]].push_back(col[_.first]);
  for(int i = 1; i <= n; i++) if(!vis[i]) deal(i), comp++;
  cout << n - ans + comp - 1 << endl;
  return cerr << "Time: " << clock() << endl, 0;
}
/*
2022/5/26
start coding at 6:41
finish debugging at 7:00
*/