Cod sursa(job #2446356)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 7 august 2019 23:38:57
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
// Matteo Verzotti - C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <ctime>
#include <map>
#include <chrono>
#include <cmath>
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a<b ? a:b

using namespace std;

/*mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long rand_seed() {
    long long a = rng();
    return a;
}*/

const int N = 100000;

vector <int> g[5 + N];
bool viz[5 + N];

int dist = 1, distmax = 1, idx;

void dfs(int nod) {
    viz[nod] = true;
    if(dist > distmax) {
        idx = nod;
        distmax = dist;
    }
    for(int i = 0 ; i < g[nod].size(); i++) {
        int vecin = g[nod][i];
        if(!viz[vecin]) {
            dist++;
            dfs(vecin);
            dist--;
        }
    }
}

int main() {
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    int n, i, x, y;
    scanf("%d", &n);
    for(i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    memset(viz,0,sizeof(viz));
    dist = distmax = 1;
    dfs(idx);
    printf("%d\n",distmax);
    return 0;
}