Cod sursa(job #3207429)

Utilizator BoggiGurau Bogdan Boggi Data 26 februarie 2024 10:34:49
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

#define pb push_back
#define PI pair<int, int>
#define VB vector<bool>
#define VP vector<PI>
#define VI vector<int>
#define VVI vector<VI>

VVI graph;
VB vis;
int n, m;
PI diam = make_pair(0, -1);

void DFS(int nod, int dist) {
    for (auto e : graph[nod]) {
        if (!vis[e]) {
            vis[e] = true;
            DFS(e, dist + 1);
        }
    }
    //cout << dist << ' ';
    if (diam.first < dist) {
        diam = make_pair(dist, nod);
    }
}

void printGraph() {
    for (int i = 1; i <= n; ++i) {
        fout << i << ": ";
        for(auto e: graph[i]) {
            fout << e << ' ';
        }
        fout << '\n';
    }
}

int main() {    
    fin >> n;
    graph = VVI(n + 1);
    for (int i = 1; i < n; ++i) {
        int x, y;
        fin >> x >> y;
        graph[x].pb(y);
        graph[y].pb(x);
    }

    //printGraph();

    vis = VB(n + 1, false);
    DFS(1, 1);
    vis = VB(n + 1, false);
    DFS(diam.second, 1);
    fout << diam.first;

}