Evtyukhov_Tipovik4_ex6

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
int n;

int bfs (int s){
    queue<int> q;
    q.push (s);
    vector<bool> used (n);
    vector<int> d (n), p (n);
    used[s] = true;
    p[s] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (size_t i=0; i<g[v].size(); ++i) {
            int to = g[v][i];
            if (!used[to]) {
                used[to] = true;
                q.push (to);
                d[to] = d[v] + 1;
                p[to] = v;
            }
        }
    }

    int mx = -2;
    for (int i = 0; i < n; i++){
        mx = max(mx, d[i]);
    }
    return mx;
}



int main(){
    n = 10;
    int m = 9;
    g.resize(n, vector<int> ());
    int help[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            help[i][j] = 0;

    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        help[a][b]++;
        help[b][a]++;
        g[a].push_back(b);
        g[b].push_back(a);
    }


    vector<int> exentricitet(n, 0);

    for(int i = 0; i < n; i++)
        exentricitet[i] = bfs(i);

    int mn = 1e8;
    for (int i = 0; i < n; i++)
        mn = min(mn, exentricitet[i]);

    cout << "CENTER " << endl;
    for (int i = 0; i < n; i++){
        if (exentricitet[i] == mn) cout << i + 1 << " ";
    }
    cout << endl;

    cout << "RADIUS " << endl;
    cout << mn << endl;

    int mx = -1;
    for(int i = 0; i < n; i++){
        mx = max(mx, exentricitet[i]);
    }

    cout << "DIAMETER " << endl;
    cout << mx << endl;

    vector<int> leaves;
    for (int i = 0; i < n; i++){
        if (g[i].size() == 1)
            leaves.push_back(i + 1);
    }

    cout << "LEAVES " << endl;
    for (auto x: leaves) cout << x << " ";

}
/*
1 2
1 5
1 3
2 4
2 6
3 7
4 8
6 9
5 10
*/