Codeforces 1092E Minimal Diameter Forest

Minimal Diameter Forest

首先我们找出每个连通块中的特殊点， 特殊点的定义是到各种个连通块中距离的最大值最小的点，

每个连通块肯定通过特殊点连到其他连通块， 我们把有最大值的特殊点当作根， 然后其他点直接接在这个点中， 形成菊花图。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, m, cnt, mx, DIA, belong[N], mn[N], who[N], id[N], dia[N];

vector<int> G[N];

void dfs(int u) {

    belong[u] = cnt;

    for(auto& v : G[u])

        if(!belong[v]) dfs(v);

}

void dfs2(int u, int fa, int depth) {

    mx = max(mx, depth);

    for(auto& v : G[u])

        if(v != fa) dfs2(v, u, depth + );

}

bool cmp(const int& x, const int& y) {

    return mn[x] > mn[y];

}

int main() {

    memset(mn, inf, sizeof(mn));

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; i++) {

        int u, v; scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    for(int i = ; i <= n; i++) {

        if(!belong[i]) ++cnt, dfs(i);

    }

    for(int i = ; i <= n; i++) {

        mx = ;

        dfs2(i, , );

        if(mx < mn[belong[i]]) {

            mn[belong[i]] = mx;

            who[belong[i]] = i;

        }

        dia[belong[i]] = max(dia[belong[i]], mx);

    }

    for(int i = ; i <= cnt; i++) {

        id[i] = i;

        DIA = max(DIA, dia[i]);

    }

    sort(id + , id +  + cnt, cmp);

    if(cnt >= ) DIA = max(DIA, mn[id[]] + mn[id[]] + );

    if(cnt >= ) DIA = max(DIA, mn[id[]] + mn[id[]] + );

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

    for(int i = ; i <= cnt; i++) printf("%d %d\n", who[id[]], who[id[i]]);

    return ;

}

/*

*/