Cod sursa(job #2571619)

Utilizator RaresLiscanLiscan Rares RaresLiscan Data 5 martie 2020 08:55:27
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

int t[100005];
vector <int> v[100005];
int parcurs[100005];

bool verificare(int a, int b)
{
    int n = v[a].size();
    for (int i = 0; i < n; i ++) {
        if (v[a][i] == b) return false;
    }
    return true;
}

void resetare(int n)
{
    for (int i = 1; i <= n; i ++) parcurs[i] = 0;
}

void dfs(int nod)
{
    int n = v[nod].size();
    for (int i = 0; i < n; i ++) {
        int nc = v[nod][i];
        if (parcurs[nc] == 0) {
            parcurs[nc] = parcurs[nod] + 1;
            dfs(nc);
        }
    }
}

int main()
{
    int n;
    fin >> n;
    int a, b;
    for (int i = 1; i <= n; i ++) {
        fin >> a >> b;
        if (verificare(a, b)) {
            v[a].push_back(b);
            v[b].push_back(a);
        }
    }
    parcurs[1] = 1;
    dfs(1);
    int maxim = 0, iMax = 0;
    for (int i = 1; i <= n; i ++) {
        if (maxim < parcurs[i]) {
            maxim = parcurs[i];
            iMax = i;
        }
    }
    resetare(n);
    dfs(iMax);
    maxim = 0;
    parcurs[iMax] = 1;
    for (int i = 1; i <= n; i ++) {
        if (maxim < parcurs[i]) {
            maxim = parcurs[i];
        }
    }
    fout << maxim + 1;
    return 0;
}