Minimal_Diameter_Forest.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
const int inf = 1000000;
const double eps = 1e-12;
vector<vector<int>> g;
int n;
vector<int> visited, par, origvis;
int bfs(int ini){
    queue<ii> q; q.push(ii(ini, -1));
    visited[ini] = 1; par[ini] = -1;
    origvis[ini] = 1;
    int ret = ini;
    while(!q.empty()){
        int cur = q.front().first;
        int pre = q.front().second;
        q.pop();
        visited[cur] = -1;
        for (int i = 0; i < g[cur].size(); i++) {
            int next = g[cur][i];
            if (next == pre) continue;
            if(visited[next] == -1){
                visited[next] = 1; par[next] = cur;
                origvis[next] = 1;
                q.push(ii (next, cur));
                ret = next;
            }
        }
    }
    return ret;
}

vector<int> getLongest(int x){//pii=pair<int,int>
    x = bfs(x);  x = bfs(x);
    vector<int> vm;
    vm.push_back( x );
    while(par[x] != -1){
        vm.push_back(par[x]); x = par[x];
    }
    return vm;
}
int main ( ) {
#ifdef LOCAL
    freopen("ina.txt", "r", stdin);
    freopen("outa.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int m;
    cin >> m;
    g.resize (n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back (v);
        g[v].push_back (u);
    }
    visited.assign(n, -1);
    origvis.assign(n, -1);
    par.assign (n, -1);
    vector<int> gotten;
    int pivot = -1;
    int tans = -1;
    for (int i = 0; i < n; i++) {
        if (origvis[i] == -1) {
            auto rec = getLongest (i);
            int dia;
            dia = rec.size() - 1;
            if (dia > tans) {
                tans = dia;
                pivot = rec[rec.size() / 2];
            }
            gotten.push_back(rec[rec.size()/2]);
        }
    }
    if (gotten.size() == 1) {
        cout << tans << "\n";
        return 0;
    }
    for (auto &v : gotten) {
        if (v == pivot) continue;
        g[pivot].push_back(v);
        g[v].push_back(pivot);
    }
    cout << getLongest(0).size() - 1 << "\n";
    for (auto &v : gotten) {
        if (v == pivot) continue;
        cout << pivot + 1 << " " << v + 1 << "\n";
    }
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}