[Codeforces1092E] Minimal Diameter Forest（树直径，DFS）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：http://codeforces.com/contest/1092/problem/E
给一个森林，问将这个森林连成一棵树使得新成的树直径最短。

显然，对于森林里的每一棵树，都选各自直径的中点作为树根，全部连到直径最长的那棵树的中心上就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int maxn = 1111;
int n, m;
int dep[maxn], vis[maxn], pre[maxn];
vector<int> G[maxn];
vector<pii> root;
int tot = 0;

int gao(int u) {
  int L = u, R = u;
  int v, d, len = 0;
  queue<int> q;
  set<int> id;

  vis[u] = 1; dep[u] = 0;
  id.emplace(u);
  q.emplace(u);
  while(!q.empty()) {
    u = q.front(); q.pop();
    id.emplace(u);
    for(auto v : G[u]) {
      if(vis[v]) continue;
      vis[v] = 1;
      dep[v] = dep[u] + 1;
      q.emplace(v);
    }
  }
  for(auto x : id) if(dep[x] > dep[L]) L = x;
  for(auto x : id) {
    dep[x] = 0;
    vis[x] = 0;
  }
  while(!q.empty()) q.pop();
  vis[L] = 1;
  q.emplace(L);
  while(!q.empty()) {
    u = q.front(); q.pop();
    for(auto v : G[u]) {
      if(vis[v]) continue;
      vis[v] = 1;
      dep[v] = dep[u] + 1;
      pre[v] = u;
      q.emplace(v);
    }
  }

  for(auto x : id) if(dep[x] > dep[R]) R = x;
  for(auto x : id) len = max(len, dep[x]);
  bool flag = 0;
  while(pre[R] != -1) {
    if(dep[R] == max(len/2, len-len/2)) {
      root.emplace_back(R, len);
      flag = 1;
      break;
    }
    R = pre[R];
  }
  if(!flag) root.emplace_back(R, len);
  return len;
}

signed main() {
  // freopen("in", "r", stdin);
  int u, v;
  while(~scanf("%d%d", &n,&m)) {
    tot = 0;
    for(int i = 1; i <= n; i++) G[i].clear();
    root.clear();
    memset(pre, -1, sizeof pre);
    memset(vis, 0, sizeof vis);
    memset(dep, 0, sizeof dep);
    for(int i = 0; i < m; i++) {
      scanf("%d%d",&u,&v);
      G[u].emplace_back(v);
      G[v].emplace_back(u);
    }
    for(int i = 1; i <= n; i++) {
      if(!vis[i]) gao(i);
    }
    int rt = 1, len = -1;
    sort(root.begin(), root.end(), [](pii a, pii b) {
      return a.second > b.second;
    });
    rt = root[0].first, len = root[0].second;
    vector<pii> edge;
    for(auto p : root) {
      if(p.first == rt) continue;
      edge.emplace_back(rt, p.first);
      G[rt].emplace_back(p.first);
      G[p.first].emplace_back(rt);
    }
    memset(vis, 0, sizeof vis);
    memset(dep, 0, sizeof dep);
    printf("%d\n", gao(rt));
    for(auto x : edge) printf("%d %d\n", x.first, x.second);
  }
  return 0;
}